Influence without Authority: Maximizing Information Coverage in Hypergraphs

目录 DM

Influence maximization,影响力最大化,是信息传播相关的一个经典问题,差不多发展有 20 年。传统的影响力最大化工作,主要是基于普通图,寻找到 k 个种子,最大化它们的影响力。即便如此,它也产生了非常多的变体,模型也趋于复杂。

跳出这个问题本身,可以发现很多相关的工作,并不能提供一个真实的验证场景。如何量化用户传递信息的概率,以及被激活的概率,是无法回避的问题。真实世界的社交网络中,可以获得很多额外数据,进而给用户画像,并得到量化后的数值。然而,科研工作很难做到这一步。这是无解的一个部分,除非去公司。

可不可以找一个好的问题切入角度,做模型简单优雅又比较有创新的工作?我从前几年的一篇 information coverage 工作中得到一些启发:既然很难去判断用户是否被激活,那为什么不考虑信息传播能达到的最大覆盖,也就是只考虑信息传达,而不考虑后续的激活等一系列操作。于是,我做了这个 超图上信息覆盖最大化 的工作。简单来说,就是 找哪几个微信群转发信息,最后更可能达到 10w+。

问题还是传统问题,但选取的是一个比较新的场景,问题分析,到解决,都做的比较扎实。自我评价为 A。

好问题+牛逼的方法,A+

好问题+经典方法,A

经典问题+牛逼的方法,A+

经典问题+经典方法,B+

《随椋鸟飞行》

目录 Life

这本书从关于椋(liang)鸟的飞行开始介绍,穿插进作者科研生涯的一些感悟。

书摘两则:

相互作用几乎只发生在相邻最近的个体之间。

鸟阵边缘的密度与中心的密度相比, 几乎高了30%。椋鸟越是靠近鸟阵边缘 就互相离得越近,越接近中心则离得越 远。这有点像在拥挤的公共汽车上,越是靠近车门,乘客就越密集,刚上车的 人、要下车的人,甚至连要继续留在车上的人都挤在车门旁边。

滴水穿石

目录 Life

投了一年多的工作,总算接收了。经历了改实验,改写作,继续改写作,等等。

做扎实的工作,这个初衷幸好坚持下来了。我也会一直坚持下去。

好的坏的都看过

目录 Life

把硕士遗留下来的两份工作的 camera ready 提交完,感觉一个阶段彻底结束了。

硕士三年半,多出来的半年是大四下,那时候已经在实验室。最开始不知道做什么,懵懵懂懂地,老师给安排了一个方向。可惜老师自己并没在那上面投入很多,本来准备带我投一篇,结果中途夭折,后面就都是一个人来了。很长时间里,研究都进展不顺利。磕磕碰碰地走着,我在这个过程中涉猎广泛。虽然没做出什么东西来,讲过的几次组会中,有两次组会对同学们的工作有比较大的启发,实验室投出去的工作中,或多或少可以看到那两次组会的影子。对此,我还是很欣慰的。

到了研二的某个时间,必须得做出什么来,才好去申学校。在迫切的需求下,我才做出了第一份很垃圾的工作。现在看,还觉得惨不忍睹。投出去后,觉得不够,得再来一个,又是一个拼凑出来的工作。这两份工作遗留至今,才勉强被接受。看了这么久的论文,自己心里大概有杆秤,第一篇最多只是 C 会的水准,第二篇可能达到一般的 B 会。而论文是否能被接受,和当前的学术潮流,以及审稿人的品味,与很多不可控的因素都有关系,俗称看运气。

真正做得开心的工作,是为了给硕士论文凑工作量,然后突然有天蹦出来个好的问题和一个可能好的解决办法。那个问题只有一份工作做过,但做的一般,我有比较大的可能去更好地解决它。那时候,要弄申请,还有各种杂事,所以拖到硕士毕业都没完成。来到慕尼黑之后,头几个月在想新的点子,硕士的点子,如果现在发出来,也只属于硕士的工作,所以我开始并不积极。在挣扎了几个月,没想出新点子,在老师的催促下,我决定优先把那份工作完成。于是,接近两个月的时间里,对之前的算法进行了非常多的改造,加了很多新东西,最后成稿里大部分的内容是之前点子里不包括的。投出去的时候,自己并没有很大的期望,因为时间缘故,论文里有一个地方没能用实验验证,这是个 bug,如果还有机会,我想解决。意想不到的是,rebuttal 的时候,审稿人的意见普遍正面:对一个比较新的问题,提出了一个较全面的解决方法,对这个解决方法的流程中可能存在的问题,都做了说明并且提出了相应的解决策略,所以整篇论文没有明显的漏洞。再后来,这份工作幸运地一投即中。

博士第一年结束了。大部分时间都在刷论文,仿佛回到了研一那时候,都没什么成果。做科研是个厚积薄发的过程。对于数据挖掘这个领域而言,找一个好问题,相比起对一个经典问题提出新颖的解法,可能更容易发论文一些。但从贡献上来说,二者并没有高低。最优的是,对一个好问题,提出新颖的解法。这是我现在的目标。目前没有博士新工作,我还撑得住,不去灌水。能撑多久,走走看。

心情压抑的时候,我应该做什么

目录 Life

德国疫情开始的那段时间,戴口罩的义务并没有普及,为数不多的亚洲人,戴着口罩反而会引人侧目。那时候,没买到口罩的我就已经放弃公共交通了,徒步往返实验室,但时间花太久。再后来,慕尼黑大学的计算机学院开始远程办公,至今都未恢复正常工作:学院的开放时间只到下午 5 点,只在工作日开放,规定每个房间最多只有一人,食堂不开门。

种种因素的交织下,我在宿舍已经待了大半年。除了去超市买菜,周末偶尔会找一处慕尼黑的景点转转。心情愉悦的时候,大部分都是因为出了门,吹着风,晒一晒自己,或者感受一下袭面的雨水。绝大部分在宿舍的时间都是很压抑的。

日复一日的,自己做饭,独自工作的生活。因为工作没有进展,心情更加的压抑了。剖析一下自己,现在这种情况的表面原因,是因为一个人宅着太久,缺乏外界的刺激;深层原因还是因为工作不顺,负反馈加剧了内心驱动力不足,效率更低,负负没有得正。

我能做什么呢?负反馈的链条很难一下子打断,从小处来讲,活出新鲜感,增强外界刺激,是两个可行的策略。

活着,除了盲然对着电脑的时间,再就是一日三餐。

饮食方面,超市能买到的蔬菜,牛肉猪肉鸡肉,香肠,超市里有的几乎都尝试过,哦,没有自己做过沙拉,之前在食堂吃过的沙拉给了我不好的印象。目前我的做菜风格是偏辣,接下来尝试一下做淡一些、偏甜的东西。

只能在宿舍工作吗?目前是,实验室不方便去,宿舍附近也没有自习室,似乎没有公共场所可以工作。我已经接受了这个事实,但还是要想想,怎样创造一个可能提高创造性的工作环境。

增强外界的刺激,主要通过与同学的交流。实验室的两个德国人不会主动和我交流问题,我有问题会主动找相关领域的人。但更多时候,我的问题是找不到人交流的。在这里,并没有像阿邵那种思维特别发散,能融会贯通各种问题的人。再去找阿邵交流交流?看了这么久论文,也做了这么多笔记,是时候整理出一个 report,找人叨叨了。

除了学术上的交流,还是可以找朋友聊聊生活的。我也是惭愧,虽然朋友不少,但大部分都是安静躺在聊天列表里,偶尔在朋友圈互动互动。这样不行。

来慕尼黑快一年了,纪念一下没有博士新工作的一年。

哪种聪明

目录 Life

和朋友的交流,让我想到一些很有意思的事情。这些事情的核心,大概就是哪种聪明。

我做事情,是不是一定要符合自己的美学?比如:做一项工程,我是不是要做到没有一点冗余代码,写很规范的注释还有文档。这是我的美学,这样的美学有人会关心吗?客户懂吗,他只会关心我实没实现他的需求,并不关心代码的规范性。如果是正式公司,提交这样的代码,可以吗?可以呀,只要加上文档注释就好了,小公司可能到这个程度就可以了。那么冗余代码能不能去掉呀?朋友语:不能,现在软件的逆向工程这么厉害,没个准公司做的产品发布后没多久就被剽窃了,所以加点别人看不懂的制造点难度也是需要的。大公司还是很注重代码质量,所以注意分清 私活 还有 主要工作。

如果是私活,需要做的很完美,很容易维护,代码很清晰吗?这样的美学可不可以带给我很大的经济效益呢?如果我接到一个私活,写的东西只有我自己能看懂,不加注释,难以维护,但能很好的实现功能需求,一般不会出现问题。出问题的时候,用户只有找我,这样是不是能有更多的经济效益呢?

之前没仔细想过这些,我也没有在公司真正工作过,朋友说的这些引人深思。朋友是很聪明的那种,工程能力很强。他说的这些常人很难做到。

聪明是要建立在能力的基础之上:如果写个东西,三天两头出问题,谁敢找你;写个东西,可以长时间稳定运行,具有很高的容错能力,用的人才会放心。 建立在能力基础上的聪明才有价值。

当行业规范,知识产权保护等越来越完善,也许这些小聪明就没有用武之处了。当然,聪明的人总会有合适的地方释放自己的才华,而踏实,是作为普通人的我们的最大的聪明。

这些年看过的韩剧

目录 Life

关于爱情

半之半 春夜 当你沉睡时 杀了我治愈我 天气好的话,我会去找你 治愈者 匹诺曹 城市猎人 德鲁纳酒店 W-两个世界 她的私生活 经常请吃饭的漂亮姐姐 阿尔罕布拉宫的回忆

犯罪题材

信号 武法律师 监视者 浪客行 赤月青日 隧道 杀之 特殊案件专案组TEN 1&2 特殊失踪专案组:失踪的黑色M 秘密森林

关于职场

心里的声音 Life 辅佐官1&2 囚犯医生 未生 棒球大联盟 我的大叔

Workshop in Vienna

目录 DM, Life

最近一个星期在维也纳大学,参与导师与师母组织的两个组之间的交流活动,感触挺多的。

国外的学生,在文献阅读方面,并不充分;但相比起来,他们的基本功更加扎实,遇到问题,可以更快做出demo;而我可能会提出很多思路,但在有限的时间里,很难做出demo。

想到了套瓷时候的经历,一个导师提供了面试机会,给了一个问题一天的时间,我列了三个思路,但并没有实现,然后就GG了。

国外导师,某种程度上,更注重demo?idea不一定靠谱,demo至少看上去有用。

或许,我需要转换一下研究思路了。

现在至少有5个一般的点子在堆着,积极合作,尽快做点东西出来。

德国留学记 之三

目录 Life

最近发生了一件很让人失望的事情:DHL把快递送到邻居那儿了,只留下一个名字,没有留房间号,回来后,几乎敲遍了周围所有邻居的门,都没有人知道那个名字;同样,在群里问,在零层入口的住户名单上,都没有找到。往好处想,是邻居收了我的东西,然后忘记拿给我了;往坏处想,是邻居提供了一个假名给快递员,而这个马虎的快递员没有提供房间号,导致没法找到人。

有些生气。因为病毒疫情,所以我买的是口罩。现在在线下店里已经买不到口罩了,线上买,我可能也是购买的最后一批。想再买也很难了。

想到还有一次被骗的经历:在食堂给别人刷卡,留了联系方式说用PayPal转账,后面对方并没有转。

在国内这么多年,碰到过态度差的人,不文明的人,满嘴跑火车的人,但像这种不诚信的,挺少。

见识了德国和德国人的各种不靠谱,失望挺多。希望是自己给自己的,好好加油。

德国留学记 之二

目录 Life

前段时间,科研有了一些进展,参与了小伙伴开启的事业。不愿让时光虚度,仍需砥砺前行。

记录一些碎碎念:

唯有发展,只有发展,才能获得更多理解与认同。

何为公民,何为公民精神?

因为参与的事业,产生了很多的碎片化思考过程,这个情况很不利。怎么应对?

在德国看到的,有些人,一辈子都在做同一件事,开公交车,一辈子在开公交车,做秘书,一辈子都在做秘书。职业的流动性相比国内,很小很小。所谓专业,所谓工匠精神,固然与这长年累月的积累有关。但它是否真的适合社会的发展?学习的广度与深度,如果不可兼得,是否应优先学习的深度?

德国留学记 之一

目录 Life

从9.1下飞机,在慕城已两月有余。除去最开始上语言班的一个月,后续的工作生活都有些艰辛。

组里做的东西很传统,近两年并没有顶会发表。独立选择的方向,是硕士研究的延续,虽然已经可以勉强自力更生,在没有思路的时候,还是很痛苦。

我太急切了,看到身在美国、新加坡和香港的同学都已经有顶会发表,羡慕之余,内心的自我驱动在一点一点加强。

沉住气。

纽约时间比加州时间早三个小时,
New York is 3 hours ahead of California,

但加州时间并没有变慢。
but it does not make California slow.

有人22岁就毕业了,
Someone graduated at the age of 22,

但等了五年才找到好的工作!
but waited 5 years before securing a good job!

有人25岁就当上CEO,
Someone became a CEO at 25,

却在50岁去世。
and died at 50.

也有人迟到50岁才当上CEO,
While another became a CEO at 50,

然后活到90岁。
and lived to 90 years.

有人依然单身,
Someone is still single,

同时也有人已婚。
while someone else got married.

世上每个人本来就有自己的发展时区。
Absolutely everyone in this world works based on their Time Zone.

身边有些人看似走在你前面,
People around you might seem to go ahead of you,

也有人看似走在你后面。
some might seem to be behind you.

但其实每个人在自己的时区有自己的步程。
But everyone is running their own RACE, in their own TIME.

不用嫉妒或嘲笑他们。
Don’t envy them or mock them.

他们都在自己的时区里,你也是!
They are in their TIME ZONE, and you are in yours!

生命就是等待正确的行动时机。
Life is about waiting for the right moment to act.

所以,放轻松。
So, RELAX.

你没有落后。
You’re not LATE.

你没有领先。
You’re not EARLY.

在命运为你安排的属于自己的时区里,一切都准时。
You are very much ON TIME, and in your TIME ZONE Destiny set up for you.

近期思考-20190129

目录 Life

回家刚好一周了,写毕业论文也一周了。硕士论文是关于 多标签学习与度量学习,问题比较传统。写前面部分的时候,发现自己对多标签学习还是不够了解,或者说是没有形成系统,写着写着,自己大概理出了几条线,对这个研究方向的认知也更加深刻了。

以上还是比较常规的,可以预想的东西。没有预想到的是,我之前认为的夕阳研究方向,可以从一些新的视角看待。

印象最深刻的是“SGM: Sequence Generation Model for Multi-label Classification”,COLING 2018的best paper,通过序列生成模型做多标签分类。之前思考深度学习和多标签分类这样的传统研究方向结合,主要和CNN相关,如TextCNN,做多标签文本分类问题。直到看到了这篇用Seq2Seq来做多标签分类的工作,感觉又打开了一条新的道路。

思路都不够开阔了,加油,少年,做最前沿的研究!

Visualization of My Research Interests

目录 DM


Tools

  1. Mendeley
  2. Python
  3. WordArt.com

Steps

  1. Export papers in Mendeley to bib file.
  2. Cleaning via Python nltk.
  3. Frequency counter via Python (Github)
  4. Cleaning via Python nltk.
    • remove phrases with low frequency.
    • remove meaningless phrases
  5. Import the output file to WordArt
  6. Visualization
 

Some thoughts about PhD/Job Application

目录 Life

A friend of mine invited me for an internship in Tencent today. The job is about data mining. As I was busy preparing for my PhD application, I thanked him.

I heard the news that Tencent Corporation decided to change its structure, to make the company flatter, as Alibaba did in 2015 (news said the idea was coming from Supersell, after a visit of Jack Ma to that north Europe company). What I did not anticipate was that change came so fast. They build a new department and many people are needed, so my friend told me that it’s a good chance. When everything is new, there is a higher chance to make a difference.

It was a pity, for I decided to follow my heard, to be a researcher. First, to be a PhD student.

Between the conversation, my friend said he wanted to learn some knowledge about DM/ML. From my perspective, he is a very good engineer, to be a specialist in the algorithm is not a wise choice for him. Maybe a system architect is better, where algorithm design is needed but not the core part. He agreed with me on that. Another reason is there are too many youths coming to the AI industry. It has been a boom since 2017. Some students from EE or even arts learned some algorithms, like SVM, decision tree, then they began to apply for AI jobs. Can you see bubbles flying? So terrible.

As I learned from industry friends, recommendation system, graph mining (i.e. mining on social network, knowledge graph search), CV and NLP, are what the industry generally needs, and streaming data mining would be a hot area. As a researcher, I always want my research to be useful. I am delighted for what I am doing.

Hope everything is OK.

Lecture Note of Scientometrics

目录 DM

Rectenly, Prof. Liu JianGuo, from SUFE, gave a lecture about scientometrics in our center. The content is mainly resolved to real applications, and it shows very interesting problems. The lecture has four parts:

  • Ranking of Research Institutions Based on Citation Relations
  • Research of Deep Learning Based Quantitative Trading Strategies
  • Quantitative Trading Strategies Based on the Degree of Attention of Stocks
  • Which Kinds of Disclosed Information Can Help You Get a Loan From P2P

组会随笔(2018-05-12)

目录 DM

两个报告,分别是关于轨迹中的交通流,以及深度学习在推荐系统中的应用。

由于主要是在做应用,是典型的问题驱动,所以这里仅仅列出一些有趣的问题。至于方法,我目前对深度学习不了解,所以不评述。

轨迹交通流有关的研究问题:

  • 某个地区出租车的供需预测
  • 交通灯控制(红绿灯 – 交通摄像头)

其中,第一个问题可以抽象成 时序数据上的回归问题,和传统的机器学习比较接近。第二个问题,在我自己了解到的方向中较少出现,因为是涉及到决策的东西。摄像头提供交通流数据,以此作为切换红绿灯或者红绿灯频率的决策基础,而决策也会影响下一个时间点的交通流。这个过程可以建模成强化学习。

此外,姚还提到了一些当前轨迹交通流研究的热门:

  • coordination in the transportation network
  • continual adaption with changing environment
  • events detection
  • data quality(sparsity, noise)

确实是很有趣的问题,但以实验室目前的环境,做不了。相信大部分同学都有这样的感觉,实验室研究的东西,虽然还是数据挖掘的主流方向,但已经脱离应用很远了;至于数据挖掘的基础理论研究,也不见得做的有多深入,因此处于很尴尬的境地。

失落会有一些,但乐观一点想,我们在研究的问题,至少是自己喜欢的,很好奇的问题。即使目前看,它对于学科的发展和社会的推动毫无作用。但我们自己还是在前进,每次向前走一点点,也是一件开心的事情。

何况,目前的环境和研究的内容,对于长期发展,还是存在一定的帮助:

虽然研究的内容是传统的数据挖掘与机器学习,以shallow model为主,但其中涉及到的基础问题也是DL中关注的问题。与一开始就做DL的同学相比,我们对于各种基础理论的学习,如压缩感知,线性代数,各种凸优化非凸优化;以及一些不入流的“小技巧”,锚点的学习,信息的传播和最大化间隔,等等;要更加熟悉。这些思想,在DL中也存在,也还待发掘。保持一种积极学习的心态,兼收并蓄,相信长期的积累,还是会带来回报。

十年了。

Structural SVMs with its Application in Recommender System [Seminar Note]

目录 DM
Paper Sharing: Predicting Diverse Subsets Using Structural SVMs [ICML’08]

Motivation
Diversity in retrieval tasks, reduces redundancy, showing more information.
e.g. A set of documents with high topic diversity ensures that fewer users abandon the query because no results are relevant to them.
In short, high diversity will cover more needs for different users, though the accuracy may not be good.

Preliminary
Candidate set: x = {x_i}, i = 1 … n
Topic set: T = {T_i}, i = 1 … n; T_i contains x_i, different topic sets may overlap.

Idea
The topic set T is unknow, thus the learning problem is to find a function for predicting y in the absence of T.
Is T the latent variable ??
– In general, the subtopics are unknown. We instead assume that the candidate set contains discriminating features which separates subtopics from each other, and these are primarily based on word frequencies.
The goal is to select K documents from x which maximizes subtopic coverage.

Keypoint: Diversity -> Covering more subtopics -> Covering more words

Method Overview

D1, D2, D3 are three documents, V1, V2, … , V5 are words.
weight word importance (more distinct words = more information)

After D1 is selected in the first iteration, which covers V3, V4, V5;
In the second iteration, we only focus on V1 and V2.

Remark:
– Feature space based on word frequency
– Optimizes for subtopic loss (Structural-SVM)

The process of this model is sophisticated. Feature space is based on word frequency, and it further divided into “bag of words” (subtopic).

From my point of view, a reason should be: each document has too many words, so dividing document into subtopics is reasonable, and this approach will reduce the overlapping between subtopics of different documents.
In each iteration, we learn the most representative subtopic, then choose the related document until we get K documents.

Remark: Structural-SVM repeatedly finds the next most violated constraint until set of constraints is a good approximation.

Comments
This paper is very interesting.
My doubts are:

  1. Can frequency of word reflect the true relevance of the document to a certain topic?
  2. How to find subtopics?

Further Reading
Learning to Recommend Accurate and Diverse Items [WWW’17]

An Intro to Subspace Clustering [Seminar Note]

目录 DM

Subspace Clustering


For the generation of clusters, often a part of features are relevant, especially for the high dimensional data. From this point of view, a number of clustering methods are proposed to find clusters in different subspaces within a dataset.

Two Perspectives

  • There exists subspace in data, so we search for the most representative feature subsets.
  • As there are clusters in different subspaces, features are more dense in each subspace cluster. Instance within a cluster can be represented by other instances within the same cluster. From this perspective, we seek to learn a representation of data, which yield X=XC.

The first perspective motivates many data mining algorithms (see survey by Parsons L. et. [1]). But due to the complexity of those algorithms, they can not handle large scale datasets. Recently, the majority of subspace clustering researchs are considering from the second perspective. By making different assumptions: the sparsity or the low-rank property, these methods can be generally divided into sparse subspace clustering [2] or low-rank subspace clustering [3].

Note that learning a representation of itself in the form of X=XC is very simple. To improve this model, a sort of algorithms consider using dictionary learning in subspace clustering, to learn a clean dictionary and an informative code, which yield X=DC. That is a big topic, see survey by Zhang Z. etc. [4] and survey by C Bao. etc [5].

Paper Sharing: Deep Adaptive Clustering [6]


Motication
In image clustering, existing methods often ignore the combination between feature learning and clustering.

Method
DAC is based on deep network, so we just give the flowchart. Firstly, a trained ConvNet is given to generate features, which guarantee the basic capacity of separation. Based on the learned features, traditional similarity learning is applied to find similar pairs and dissimilar pairs, similar to must-link and cannot-link in network mining. After obtaining those constraints, DAC goes back to train the ConvNet. That is one iteration.

The hint of DAC are that:

  • It adopts a classification framework for clustering.
  • The learned features tend to be one-hot vectors by introducing a constraint into DAC. Thus clustering can be performed by locating the largest response of the learned features.

Doubts
The performance of DAC is strongly dependent on the initialization of ConvNet. It is learned by another method.

Others
There are other ideas that using “supervised” model to clustering task. For example [7]

References

[1] Parsons L, Haque E, Liu H. Subspace clustering for high dimensional data: a review[J]. Acm Sigkdd Explorations Newsletter, 2004, 6(1): 90-105.

[2] Elhamifar E, Vidal R. Sparse subspace clustering[C]//Computer Vision and Pattern Recognition, 2009. CVPR 2009. IEEE Conference on. IEEE, 2009: 2790-2797.

[3] Vidal R, Favaro P. Low rank subspace clustering (LRSC)[J]. Pattern Recognition Letters, 2014, 43: 47-61.

[4] Zhang Z, Xu Y, Yang J, et al. A survey of sparse representation: algorithms and applications[J]. IEEE access, 2015, 3: 490-530.

[5] Bao C, Ji H, Quan Y, et al. Dictionary learning for sparse coding: Algorithms and convergence analysis[J]. IEEE transactions on pattern analysis and machine intelligence, 2016, 38(7): 1356-1369.

[6] Chang J, Wang L, Meng G, et al. Deep Adaptive Image Clustering[C]//Proceedings of the IEEE Conference on Computer Vision and Pattern Recognition. 2017: 5879-5887.

[7] Liu H, Han J, Nie F, et al. Balanced Clustering with Least Square Regression[C]//AAAI. 2017: 2231-2237.