随笔(四)— 社交网络平台的时间线

在社交网络上,除了日常可以与朋友聊天沟通之外,还可以发各种内容,包括 QZone 的说说/图片,也包括人人或者 Facebook 的 Timeline,印象深刻的就是人人的“历史上的今天”,还有 Facebook 的“那年今天”。于是,回顾自身社交网络的时候,突然看到历史上的自己在某天发表过某个内容,其实也是一件挺有意思的事情。

2013 年 1 月 30 日

微信公众号 20130130

在 2013 年 1 月 30 日这天,笔者在微信公众号发表了第一个朋友圈,图中展示了在做助教的时候,中途下课期间去 Faculty of Engineering 打饭,然后拿到办公室去吃的场景。NUS 工学院的食堂算是 NUS 比较大的食堂之一,其吃饭的地方也比较多。该食堂历史悠久,从 1983 年到 2018 年。后续已经重建,直到 2020 年才正式对外重新开放。

Faculty of Engineering Canteen

2013 年 11 月 16 日

微信公众号 20131116

Marina Bay Sands 一直是新加坡比较有名的酒店之一,其特点就是在其酒店的屋顶有一个无边的游泳池,入住酒店的旅客可以免费上去游玩。那天一位同学的亲戚来新加坡旅游并且入住 Marina Bay Sands,亲戚走了之后就将第二天可以上去的门票留给了同学,于是朋友就邀请我上去游玩了一次。虽然笔者小时候会游泳,但是也已经多年没有下过水,为了这次游玩还专门去商店买了一套游泳装备。到了可以游玩的当天,就跟着同学一起去了 Marina Bay Sands,从下午开始一直待到晚上 8:00 左右,欣赏了新加坡滨海湾从白天,到傍晚,再到夜晚的风景。整体来看,Marina Bay Sands 的无边游泳池还是非常赞的,非常值得再去一次。

2014 年 2 月 28 日

2014年2月28日

当年作为一个博士生,除了吃喝玩乐之外,最主要的任务自然就是科研了,记得在 2014 年的时候,正好是科研压力比较大的时期,每天晚上都要科研到深夜,自然过年期间也不例外。NUS 的开学期间算是相对较早的,每年的 1 月初就已经开启了新的学期,Chinese New Year(农历新年)正好处于学期中间,因此,作为博士生的话回家就不是那么方便,于是过年期间可能会休息一两天,然后就必须要投入紧张的科研工作中了。在 2014 年 2 月底,笔者也工作到凌晨,但是的科研内容主要是复动力系统相关,日常主要是大量而繁重的计算。计算的时候除了动笔之外,还可以把日常的工作内容用 LaTex 敲写下来,方便未来查看与翻阅。当时的工作地点主要在 PGPR 的宿舍,工作的工具包括一台 2012 年的 MAC AIR,一堆草稿纸,铅笔和橡皮。使用铅笔与橡皮可以让自己出错的时候及时修改,也是为了克服自己内心深处避免错误的恐惧。

2015 年 2 月 13 日

微信公众号 20150213

经过去年一年的努力科研,转眼到了 2015 年。而在 2014 – 2015 这一年内,笔者顺利地完成了科研课题,并且提交了博士论文。在 2014 年的时候,笔者曾经写下 2015 年回家过年的新年愿望。经过了一年的努力,终于达成目标,成功在 2015 年回到贵州遵义欢度新年。虽然当时其实也没有完成毕业答辩,也没有找好工作,甚至都没有想好找什么工作,但是能够顺利提交论文,对笔者来说就是一件值得庆祝的事情。

2015 年 5 月 15 日

微信公众号 20150515

在 2015 年 4 月份完成了博士毕业答辩,并且提交完了最后的材料之后,博士生涯基本上告一段落,此刻再也不需要研究数学课题,也不需要思考数学论文。在人生的一个阶段即将结束的时候,也就是快要离开新加坡的时候了,此刻笔者去了之前一直都没去过的东海岸公园(East Coast Park)徒步,独自一人沿着东海岸公园的海岸线走了很长的一段路,期间见过很多烧烤架,也看到不少的游人在此游玩。其实作为动力系统的博士生,每次见到海滩,就想到 Smale 当年在沙滩上思考动力系统的场景。虽然自身的水平明显不如 Smale,但是能够从事过近似的一个研究方向,也算是一种荣幸吧。

2016 年 7 月 20 日

微信朋友圈 20160720

2016 年去台湾,已经是加入公司一周年的事情了,在这一周内里面发生了太多的事情。一开始需要面对工作上的辛苦,后来需要处理各种各样的事情,直到后续的购房安家装修工作,很多事情都在 2016 年完成。不过,2016 年的台湾之行总是给自己留下了一个还不错的回忆,以至于后面连续三年都去台湾旅游,台北,台中,台南,台东都走了一遍甚至多遍。这次去台湾除了在跟团游方面比较省心之外,还在台湾大学数学系见到了之前的博士同学,共同探讨了一些毕业之后的事情和发展情况,虽然自己已经不再从事数学研究,但是能够认识一些数学界的朋友,也算是人生的一种经历。

2017 年 5 月 28 日

微信朋友圈20170528

近些年去过不少的地方,包括厦门,长沙,武汉,上海,北京,广州等,也包括中国台湾,韩国济州岛,老挝,日本。其中海外旅游还是日本比较好,无论是从旅游设施的便捷程度,还是服务质量等方面来看,都是日本最佳。去日本的话基本上还是赶凌晨的飞机前往,因此需要提前一天从深圳过关去香港,然后再从香港飞往日本。在 2017 年第一次去日本的时候,由于太过疲惫,就在日本的新宿御苑的草坪上睡了一觉,直到下午才见到“一边旅游一边写诗“的博主司北。自从南大毕业之后,在新加坡见过一次司北,时隔多年,在日本东京又再次见到。依稀记得,当时是带了一本很厚的摄影书籍给司北,然后在四谷附近的居酒屋吃了一顿晚饭。

2017 年 9 月 10 日

微信朋友圈20170910

这已经是第二次来台湾旅游了,第二次来的时候,之前在台北做博士后的朋友已经回大陆顺利找到了教职,因此没有在台北见面。这次来台湾旅游主要是在台北,台东,台南旅行。旅行结束之后,自己的工作内容其实也发生了变化,后续就主要从事智能运维(AIOps)方向,一干就是三年时光,直到 2020 年才再一次发生了变化。不过第二次来台湾其实已经没有了第一次的新鲜劲,但是不一样的景点还是给我留下了深刻的印象,也让我意识到其实下一次来台湾就完全可以自由行了。

2018 年 12 月 29 日

微信朋友圈20181229

作为一直在南方生活的人来说,虽然在冬天也能够看到雪,但是南方的雪和北方的雪比起来还是弱了不少。在 2019 年元旦之际,笔者和 RDD 同学选择了去北海道旅游。北海道位于日本的东北部,是著名的旅游景点,无论是春夏秋冬,都有其非常出名的景色。但最吸引人的应该就是北海道的雪景。从札幌开始,走过旭川,登别,洞爷,函馆,小樽,北海道每一个地方的景色都给我们留下了深刻的印象。不过北海道的白天较短,16:00 之后就基本上进入了夜色,对于想要出行的朋友可以趁早出发,然后晚上就可以早点休息。(未完待续)

Sponsored Post Learn from the experts: Create a successful blog with our brand new courseThe WordPress.com Blog

WordPress.com is excited to announce our newest offering: a course just for beginning bloggers where you’ll learn everything you need to know about blogging from the most trusted experts in the industry. We have helped millions of blogs get up and running, we know what works, and we want you to to know everything we know. This course provides all the fundamental skills and inspiration you need to get your blog started, an interactive community forum, and content updated annually.

复杂网络中的节点相似性

在机器学习领域,很多时候需要衡量两个对象的相似性,特别是在信息检索,模式匹配等方向上。一般情况下,相似性与距离是都是为了描述两个对象之间的某种性质。但在实际使用的时候,需要根据具体的情况来选择合适的相似度或者距离函数。

相似性与距离

首先,我们来看一下相似性函数的含义。对于两个对象 x,y \in X, 相似性函数 s:X\times X\rightarrow \mathbb{R} 是将 X\times X 映射到实数域 \mathbb{R} 的有界函数,i.e. 存在上下界使得 s_{min}\leq s\leq s_{max}, 它具有以下两个性质:

  1. 自反性:s(x,x)=s_{max} 对于所有的 x\in X 都成立;
  2. 对称性:s(x,y)=s(y,x) 对于所有的 x,y\in X 都成立;

一般情况下,不要求相似度函数具有三角不等式的性质。相似度越大,表示两个元素越相似;相似度越小,表示两个元素越不相似。

相似度

其次,我们来看一下距离函数的含义。对于两个对象 x,y\in X, 距离函数 d:X\times X\rightarrow \mathbb{R}^{+}\cup\{0\} 是将 X\times X 映射到非负实数域的函数,它只存在下界 0, 并不存在上界,它具有以下三个性质:

  1. 自反性:d(x,x)=0 对于所有的 x\in X 都成立;
  2. 对称性:d(x,y)=d(y,x) 对于所有的 x,y\in X 都成立;
  3. 三角不等式:d(x,y)+d(y,z)\geq d(x,z) 对于所有的 x,y,z\in X 都成立。

距离越小,表示两个元素越近;距离越大,表示两个元素越远。

距离

相似度(Similarity)

对于欧式空间 \mathbb{R}^{n} 中的两个点 A=(a_{1},a_{2},\cdots,a_{n})B=(b_{1},b_{2},\cdots,b_{n}) 而言,可以多种方法来描述它们之间的相似性。

余弦相似度(Cosine Similarity)

\text{Cosine Similarity}(A,B)=\frac{A\cdot B}{||A||_{2}\cdot ||B||_{2}}=\frac{\sum_{i=1}^{n}a_{i}b_{i}}{\sqrt{\sum_{i=1}^{n}a_{i}^{2}}\cdot\sqrt{\sum_{i=1}^{n}b_{i}^{2}}}.

根据 Cauchy 不等式可以得到 Cosine Similarity 的取值范围是 [-1,1].

Pearson 相似度(Pearson Similarity)

\text{Pearson Similarity}(A,B)=\frac{cov(A,B)}{\sigma_{A}\cdot\sigma_{B}}=\frac{\sum_{i=1}(a_{i}-\overline{A})\cdot(b_{i}-\overline{B})}{\sqrt{\sum_{i=1}^{n}(a_{i}-\overline{A})^{2}}\cdot\sqrt{\sum_{i=1}^{n}(b_{i}-\overline{B})^{2}}}.

其中 \overline{A}=\sum_{i=1}^{n}a_{i}/n, \overline{B}=\sum_{i=1}^{n}b_{i}/n. 同样根据 Cauchy 不等式可以得到 Pearson Similarity 的取值范围是 [-1,1].

Pearson 系数

Dice 相似度(Dice Similarity)

\text{Dice Similarity}(A,B)=\frac{2\sum_{i=1}^{n}a_{i}b_{i}}{\sum_{i=1}^{n}(a_{i}^{2}+b_{i}^{2})},

其中 AB 不能同时是零点,并且由均值不等式可以得到 Dice Similarity 的范围也是 [-1,1].

除了欧式空间的点之外,在有的情况下需要对两个集合 AB 来做相似度的判断。特别地,欧式空间 \mathbb{R}^{n} 里面的点可以看成 n 个点所组成的集合。因此,下面的集合相似度判断方法同样适用于欧式空间的两个点。

Jaccard 相似度(Jaccard Similarity)

对于集合 AB 而言,

\text{Jaccard Similarity}=\frac{|A\cap B|}{|A\cup B|} = \frac{|A\cap B|}{|A|+|B|-|A\cap B|},

其中,|\cdot| 表示集合的势,并且 Jaccard 相似度的取值范围是 [0,1]. 越靠近 1 表示两个集合越相似,越靠近 0 表示两个集合越不相似。

两个集合 A 和 B

重叠相似度(Overlap Similarity)

对于集合 AB 而言,

\text{Overlap Similarity}=\frac{|A\cap B|}{\min\{|A|, |B|\}}

= \max\bigg\{\frac{|A\cap B|}{|A|}, \frac{|A\cap B|}{|B|}\bigg\}

= \max\{P(B|A), P(A|B)\},

其中 P(B|A), P(A|B) 指的是条件概率,意思分别是 A 发生的时候 B 同时发生的概率,B 发生的时候 A 同时发生的概率。重叠相似度的另外一个名称是 Hub Promoted(HP),它主要用于计算两个集合的重叠程度。

Overlap Similarity

类似的,可以将重叠相似度中的 min 函数换成 max 函数,那就是所谓的 Hub Degressed(HD),用公式来描述就是

\text{HD}(A,B)=\frac{|A\cap B|}{\max\{|A|,|B|\}},

它可以用于描述两个集合不重叠的程度。

距离(Distance)

欧氏距离(Euclidean Distance)

d_{2}(A,B)=\sqrt{\sum_{i=1}^{n}(a_{i}-b_{i})^{2}}.

另外,如果将 2 进行推广,则可以引导出 L^{p}(1\leq p\leq  +\infty) 距离如下:

d_{p}(A,B)=\bigg(\sum_{i=1}^{n}|a_{i}-b_{i}|^{p}\bigg)^{\frac{1}{p}}, 其中 p\geq 1.

d_{\infty}(A,B)=\max_{1\leq i\leq n}|a_{i}-b_{i}|.

欧氏距离

复杂网络中的节点相似性

在复杂网络 G=(V,E) 中,G 表示顶点集合,E 表示边的集合。为了简单起见,这里暂时是考虑无向图的场景。对于顶点 x \in V 而言,N(x) 表示其邻居的集合。在复杂网络中,同样需要描述两个顶点 x,y\in V 的相似性,于是可以考虑以下指标。

无标度网络

共同邻居相似度(Common Neighbours Similarity)

对于两个顶点 x,y\in V 而言,如果它们的共同邻居数越多,表示它们的相似度越高,反之,相似度越低。

CN(x,y)=|N(x)\cap N(y)|=\sum_{u\in N(x)\cap N(y)}1.

共同邻居

所有邻居相似度(Total Neighbours Similarity)

类似地,将顶点 xy 的邻居求并集,也可以得到一个指标,TN(x,y)=|N(x)\cup N(y)|.

Preferential Attachment

PA(x,y)=|N(x)|\cdot |N(y)|, 它将 xy 的邻居数乘起来,获得一个指标。

Jaccard 相似度(Jaccard Similarity)

如果将两个节点 xy 的邻居分别作为两个集合 N(x), N(y), J(x,y)=CN(x,y)/TN(x,y) 就可以作为顶点 xy 的 Jaccard 相似度指标,其相似度是通过邻居来衡量的。

Sorensen-Dice 相似度(Sorensen-Dice Similarity)

SI(x,y)=\frac{2|N(x)\cap N(y)|}{|N(x)|+|N(y)|},

该相似度与 Jaccard 相似度有恒等变换,J(x,y)=\frac{SI(x,y)}{2-SI(x,y)}SI(x,y)=\frac{2\cdot J(x,y)}{1+J(x,y)}.

Hub Promoted 相似度

该相似度描述了顶点 xy 的重叠程度,

HP(x,y) = \frac{|N(x)\cap N(y)|}{\min\{|N(x)|,|N(y)|\}}.

Hub Depressed 相似度

HD(x,y)=\frac{|N(x)\cap N(y)|}{\max\{|N(x)|,|N(y)|\}}.

复杂网络的社区

好友度量(Friend Measure)

\text{Friend-measure}(x,y)=\sum_{u\in N(x)}\sum_{v\in N(y)}\delta(u,v),

其中 \delta 用于判断 u,v 之间是否有边相连接。如果相连接,则取值为 1, 否则取值为 0.

Adamic Adar 相似度(Adamic Adar Similarity)

A(x,y)=\sum_{u\in N(x)\cap N(y)}\frac{1}{\ln |N(u)|},

因此,0\leq A(x,y)\leq \frac{CN(x,y)}{\ln(2)}. 事实上,当 u\in N(x)\cap N(y) 时,|N(u)|\geq 2. A(x,y) 越大,表示顶点 xy 的相似度就越高;反之,如果 A(x,y) 越小,表示顶点xy 的相似度就越低。Adamic Adar Algorithm 相当于在共同邻居的计算上增加了权重,如果 x,y 的共同邻居 u 拥有较多的邻居,则降低权重,否则增加权重。

Resource Allocation 相似度(Resource Allocation Similarity)

RA(x,y)=\sum_{u\in N(x)\cap N(y)}\frac{1}{|N(u)|},

该相似度函数与 Adamic Adar 相似度类似,只是分母上没有增加对数函数而已。

参考文献:

  1. Silva, Thiago Christiano, and Liang Zhao. Machine learning in complex networks. Vol. 2016. Switzerland: Springer, 2016.
  2. Barabási, Albert-László. Network science. Cambridge university press, 2016.
  3. Wang, Peng, et al. “Link prediction in social networks: the state-of-the-art.” Science China Information Sciences 58.1 (2015): 1-38.

在新加坡的这五年—生活篇(七)

留学在外,衣食住行是所有学生都必须要关注的事情。还未出国之前,笔者总觉得在外留学需要每天自己准备食物,然后刚到新加坡的第一天,就彻底地打消了这个念头。新加坡是一个多元化的国家,它们的饮食亦是如此,除了当年下南洋的华人所创造的诸多美食之外,还有周边国家的人民所传入的食物。除此之外,新加坡人日常工作繁忙,也少有人能够在家长期做饭。虽不能够经常在家做饭,但在新加坡的各个社区和住宅楼附近,都布满了食阁,里面充满了各国的食物,足以满足周边居民的饮食需要。

NUS 的食阁(摘选 NUS 官网)

对于学生而言,如果日常都要去周边食阁吃饭,则还是不太方便,但是在 NUS 的内部的各个学院其实都有相应的食堂。第一次到 NUS 的时候,是从 West Coast Plaza 出发,穿越 Clementi Woods,就走到了 NUS 的工学院(Faculty of Engineering)。在工学院的食堂,其实就有各个国家的食物,不仅有中式的快餐,还有印尼烧烤等诸多食物。在食堂附近,还有着一年到头都开着的麦当劳(Mcdonalds),无论是在日常生活还是除夕期间,都可以去麦当劳购买快餐。每个学院都有自己的食堂其实会相对方便,毕竟每个院系的学生和老师都在相应的院系走动,近距离的食堂确实也能够给大家带来更多的方便。当时在 NUS 当助教的时候,是带 MA1505 和 MA 1506 两门课,而这两门课的开设地点通常都是在工学院(除了在 2014 – 2015 学年改到了 UTown 的 ERC),在工学院讲课自然是在工学院吃饭最为方便。而工学院的食堂则是位于 Central Library 的对面,只要坐校车就可以轻松地到达食堂。

FacultyofEngineeringCanteen_1
Faculty of Engineering 的食堂

NUS 的工学院食堂里面的店面相对丰富,不仅包括中式杂菜饭,还有印尼烧烤等诸多选择,足以满足不少教职工的需要。毕竟新加坡是一个多元化的国家,由不同的民族组成。所谓杂菜饭,就是跟国内的食堂打饭一样的性质,商家会将不同种类的菜分门别类的放好,顾客想吃什么菜只需要告诉商家就行,最后商家会根据顾客的需要将其打包或者装盘。不过 NUS 的 Faculty of Engineering 的打包看上去就是很简单,Science 的鸡肉饭至少会用一个饭盒。

2013年1月30日的朋友圈
人生第一个朋友圈(20130130)

对于理学院的学生而言,其实去 Science 的食堂是最方便的,当年只要从理学院的大门进去,就能够很容易地找到 Science 食堂。在 2010 – 2015 年期间,Science 食堂一直维持原样,直到 2017 年底 Science 食堂才得以重新翻修。后续如果有机会重返新加坡,一定会去新的 Science Canteen 再吃一顿。

FacultyofScience_1
理学院的标志
FacultyofScienceCanteen_1
以前的 Science Canteen

除了在各个学院的食堂之外,NUS 宿舍区的食堂其实也独具特色。对于博士生而言,日常的饮食自然是可以在学院的食堂解决,但是每个学院的食堂周末都是不开门的。事实上,每次到了星期六下午 13:00 之后,各个学院的食堂都会关闭,直到下周一才会重新开始营业。于是每到周末的时候,博士生们除了选择外出吃饭之外,还可以选择在 UTown 或者 Prince George Park 的食堂吃饭。UTown 和 Prince George Park 是研究生和博士生能够选择的宿舍区,其中有很多类型的宿舍可供选择,无论是有空调的屋子,没有空调的屋子,还是家庭式的独立房间都是可以让博士生根据自身的需要进行选择的。

NUS UTown Residence

周末除了能够在宿舍区的食堂吃饭之外,学生们还可以选择去周边的食阁寻找美食。距离 NUS 比较近的住宅区是 Clementi(金文泰),而在金文泰比较有名的小吃则是“黄土地西安小吃”,这家店铺主要是卖羊肉泡馍,肉夹馍,凉皮等食物。而这些美食恰好就是 NUS 的食堂所没有的,因此数学系里面的几位西安籍的博士生都非常喜欢去这家店。从 NUS 的数学系 S17 去 Clementi 其实只需要从 AYE 上乘坐 97,197,198,963 等线路的公交车就可以顺利抵达,不过下车之后自然是需要步行一段时间的。

S17 到 Clementi 的线路

新加坡的各个住宅区都设有食阁,食阁里面的食物自然是可以提供外带服务的。有几次笔者就将凉皮和肉夹馍自行携带回 S17 的办公室享用。

星期日的晚餐(20131006

除了来自中国的面食之外,在新加坡也有不少日本拉面店。在新加坡吃日本拉面的地点也有许多,而笔者常去的地点包括 Vivo City, Buona Vista 和 Holland Village 。笔者吃日本拉面其实是受到了卫同学的影响。自从 Circle Line 开通了之后,从 NUS 的 S17 去 Vivo City 也很方便,只需要在 Kent Ridge MRT Station 乘坐 Circle Line 就可以轻松抵达 Vivo City,在这里有日本拉面店中比较出名的是面屋武藏(Menya Musashi)。同时,新加坡的荷兰村(Holland Village)也是店铺林立,它属于新加坡别有风味的休闲购物区。在荷兰村有不少的酒吧,商店,饭馆等,只要有钱有时间有胃口,在这里就可以享用到各国的美食。在 Holland Village 的拉面店也有许多,包括 Yushimura 日本拉面,三宝亭(Sanpoutei Ramen),翡翠拉面小笼包等,只不过翡翠拉面小笼包中的拉面一般是中式拉面。

面屋武藏(20131113

日常的饮食除了食堂和各个餐馆之外,各种类型的自助餐也是新加坡的特色之一。刚去新加坡的时候第一次吃的自助餐就是四川火锅自助,在 Block 602 附近就有添一点火锅和川江号子。在节假日最常做的一件事情就是在中午的时候吃自助火锅,到了晚上之后就完全不需要吃晚饭了。新加坡的自助餐除了中国的四川火锅之外,还有各种各样的海鲜自助餐。其中去的次数较多的就是维也纳海鲜,虽然说是海鲜自助餐,但是也会提供牛排,鸡翅等食物。整体的质量较高,推荐享用。

维也纳海鲜(20131019

每次到了新加坡春节的时候,包括 NUS 校园内部食堂在内的许多餐厅都会暂停营业。在这种时候,博士生们除了吃麦当劳或者自己做饭之外别无选择。不过在 NUS 的 Faculty of Engineering 就有一个麦当劳,在 Kent Ridge MRT Station 也有一个汉堡王(Burger King),每逢节假日笔者都有可能出现在这里吃汉堡。

正月初二的麦当劳(20140201)

到了 2014 年,基本上是 2010 级的博士生准备毕业的时候,毕竟这是博士生面临着发表论文和撰写毕业论文的关键阶段了。在 2014 年 7 月 12 日,2010 级第一位提交博士论文的博士生何同学离开了新加坡,准备再去美国攻读一个博士学位。在送别了何教授之后,笔者和一些朋友一起去 Geylang 的串烧工坊吃了顿烧烤。不过新加坡的啤酒是真的十分昂贵,一瓶青岛啤酒在餐馆里面可以卖到 8 新币(折合人民币 40 元左右)。

串烧工坊(20140712)

其实在 2014 年上半年,笔者的论文课题已经基本完成,关键的核心步骤已经写好。而到了 2014 年的下半年,笔者的毕业论文基本上已经写好,只需要整理完成即可。那半年的主要工作就是撰写毕业论文和当助教,到了 2015 年的时候,笔者已经顺利地提交了博士论文并且回国过春节。在 2015 年 4 月份答辩结束之后,在回国找工作之前,笔者专门去了一次位于宏茂桥的龙海鲜螃蟹王,这里的螃蟹米粉真的是一绝,螃蟹汤拌米粉真的是非常好吃。2012 年和司北吃螃蟹是在新加坡河边上的珍宝海鲜楼,后来 2017 年在日本东京的时候也与司北在日本居酒屋共进晚餐,只是不知道下次跟司北一起吃饭是在何时何地了。(未完待续)

龙海鲜螃蟹王(20150519)

随机图模型

数学家是一种把咖啡变成定理的机器。
Alfred Renyi

A mathematician is a machine for turning coffee into theorems.
Alfred Renyi

随机图的历史

在 1959 和 1968 年期间,数学家 Paul Erdos 和 Alfred Renyi 发表了关于随机图(Random Graph)的一系列论文,在图论的研究中融入了组合数学和概率论,建立了一个全新的数学领域分支—随机图论。

随机图的案例 p=0.01

随机图的定义

本文只关注无向图的场景。顾名思义,随机图(Random Graph)就是将一堆顶点随机的连接上边。好比在地上撒了一堆豆子,而豆子之间是否用线来相连是根据某个概率值来确定的。通常来说,对于随机图而言有两种定义方式

  1. 【定义一】给定 NM, G_{1}(N,M) 的定义是随机从 N 个顶点和 M 条边所生成的所有图集合中选择一个。其中,这样的图集合的势是 C(N(N-1)/2, M), 因此获得其中某一个图的概率是 1/C(N(N-1)/2, M).
  2. 【定义二】给定 NpG_{2}(N,p) 的定义是有 N 个顶点,并且两个顶点之间以概率 p\in[0,1] 来决定是否连边。

事实上,这两个定义是等价的,N 个顶点的图最多拥有的边数是 N(N-1)/2,G_{1}(N,M) 恰好有 M 条边,并且它们分配的概率是均等的,因此两个顶点之间是否存在边的概率就是 p = M/(N(N-1)/2), 这里的 C 指的是组合数。i.e.

G_{1}(N,M) = G_{2}(N, \frac{M}{N(N-1)/2}).

另一方面,对于 G_{2}(N,p) 而言,顶点两两之间是否存在边的概率是 p,N 个顶点的图最多拥有 N(N-1)/2 条边,于是边数为 pN(N-1)/2. i.e.

G_{2}(N,p)=G_{1}(N,pN(N-1)/2).

进一步地,通过以上两个公式可以得到:

G_{1}(N,M)=G_{2}(N,\frac{M}{N(N-1)/2}) = G_{1}(N,M).

在定义一中,可以直接算出所有顶点的平均度是 \langle k\rangle = 2 M /N. 但如果要计算图的其余指标,用第二种定义 G_{2}(N,p) 反而更加容易,因此后续将会重点关注第二种定义,为方便起见,记号简化为 G(N,p) = G_{2}(N,p).

随机图的度

图的度(degree)指的是对于某个顶点而言,与它相关联的边的条数。对于随机图 G(N,p) 而言,它的边数大约是 pN(N-1)/2, 最多与该节点相连接的顶点数为 N-1, 整个图的顶点平均度是(边数 * 2) / 顶点数,用记号 \langle k\rangle 来表示,意味着顶点平均度是 \langle k\rangle = p(N-1) \sim pN,N 充分大的时候成立。换言之,

p \sim \langle k\rangle / N.

顶点上的值就是该顶点的度

对于随机图 G(N,p) 中的一个顶点 i 而言,我们想计算它恰好有 d 条边的概率值。事实上,对于除了 i 之外的 N-1 个点而言,有 d 个顶点与 i 相连,N-1-d 个顶点与 i 不相连,其概率是 p^{d}(1-p)^{N-1-d}, 同时需要从这 N-1 个点中选择 d 个点,因此,顶点 i 的度恰好是 d 的概率是

p_{d}=C(N-1, d)\cdot p^{d}\cdot (1-p)^{N-1-d}.

特别地,当 d\ll N 时,上述概率近似于泊松分布(Possion Distribution)。事实上,p=\langle k\rangle / (N-1) 并且

C(N-1,d) = (N-1)(N-2)\cdots(N-d+1)/ d! \sim (N-1)^{d} / d!,

(1-p)^{N-1-d} \sim (1-\langle k\rangle /(N-1))^{N-1-d} \sim e^{-\langle k\rangle},

因此,在 d\ll N 时,p_{d} 近似于泊松分布,

p_{d} \sim \langle k\rangle^{d}e^{-\langle k\rangle}/d!.

随机图的连通分支

对于随机图 G(N, p) 而言,它的连通分支个数是与顶点的平均度 \langle k\rangle 息息相关的。特别地,当 \langle k\rangle=0 时,每个顶点都是孤立的,连通分支个数为 N;\langle k\rangle=N-1 时,任意两个顶点都有边相连接,整个图是完全图,连通分支的个数是 1. 顶点的平均度从 0N-1 的过程中,连通分支的个数从 N 演变到 1, 最大连通分支顶点数从 1 演变到 N, 那么在这个变化的过程中,最大连通分支的顶点数究竟是怎样变化的呢?是否存在一些临界点呢?数学家 Erdos 和 Renyi 在 1959 年的论文中给出了答案:

对于随机图 G(N,p) 而言,用 N_{G} 表示最大连通分支的顶点个数,那么对于图的平均度 \langle k\rangle 而言,

  1. \langle k\rangle = Np < 1, 那么 N_{G} = O(\ln(N));
  2. \langle k\rangle = Np = 1, 那么 N_{G} = O(N^{2/3});
  3. \langle k\rangle = Np \in (1, \ln(N)), 那么巨连通分支(Giant Component)存在,同时存在很多小的连通分支,在临界点 1 的附近时, N_{G} \sim (p-p_{c})N, 这里 p_{c}=1/N;
  4. \langle k\rangle = Np \in (\ln(N),+\infty), 那么图 G 是全连通图,i.e. N_{G}=N.

在这个定理中,对于顶点的平均度 \langle k\rangle 而言,存在两个临界点,分别是 1\ln(N).\langle k\rangle < 1 时,巨连通分支不存在,所有连通分支的量级都在 O(\ln(N)) 以下;当 \langle k\rangle = 1 时,巨连通分支开始出现,量级大约是 O(N^{2/3});1<\langle k\rangle <\ln(N) 时,随机图存在一个巨连通分支和很多小的连通分支;当 \langle k\rangle > \ln(N) 时,图是连通图。

图的平均度的临界点

整个定理的证明有点复杂,但本文将会介绍两个临界点的计算。先来考虑第一个临界点 \langle k\rangle = 1 的情况:

N_{G} 来表示随机图 G 中的最大连通分支的顶点个数,u 表示图 G 中不在最大连通分支的顶点比例,i.e.

u=(N-N_{G})/N = 1 - N_{G}/N= 图的顶点不在最大连通分支的概率。

对于不在最大连通分支的顶点 i 而言,其余的 N-1 个顶点分成两种情况,Case(1):要么 i 与之不相连,此时概率是 1-p; Case(2):要么 i 与之相连,但此时的顶点不能在最大连通分支中,那就只能在剩下的 uN 个顶点中,其概率是 pu. 于是,对于所有顶点而言,它不在最大连通分支的概率是 (1-p+pu)^{N-1}. 于是,

u=(1-p+pu)^{N-1}=(1-p(1-u))^{N-1}.

根据 p\sim\langle k\rangle /N\lim_{N\rightarrow +\infty}(1+x/N)^{N}=e^{x} 可以得到当 N 充分大时,有

u = (1-p(1-u))^{N-1} = (1-(1-u)\langle k\rangle /N)^{N-1} \sim e^{-(1-u)\langle k\rangle}.

s= 1-u = N_{G}/N, 它表示最大连通分支的顶点个数在所有顶点个数的占比,从而可以得到近似方程

1-s=e^{-\langle k\rangle s}.

g(s) = 1 - s - e^{-\langle k\rangle s},g(0) = 0, g(1) = -e^{\langle k\rangle}<0. 它的导数是 g'(s) = - 1 + \langle k\rangle e^{-\langle k\rangle s}, 通过计算可以得到:

  1. \langle k\rangle \leq 1 时,g'(s)<0(0,1) 上成立,i.e. g(s) = 0[0,1] 上的唯一解是 s=0, 换言之,N_{G}/N = s \rightarrow 0;
  2. \langle k\rangle > 1 时,g'(s)>0(0,\ln\langle k\rangle/\langle k\rangle) 成立,g'(s)<0(\ln\langle k\rangle /\langle k\rangle,1) 成立。换言之,g(s)=0[0,1] 上除了零之外还有解 s_{0}\in(0,1). 此时会存在巨连通分支,N_{G}/N = s_{0}\in (0,1) 是解。

因此,最大连通分支的顶点数在这个点会出现突变,1 是该方程的第一个临界点,并且是出现巨连通分支的临界点。

再来考虑第二个临界点 \langle k\rangle = \ln(N) 的情况。对于极限状况而言,假设仅有一个顶点不在最大连通分支中,那么 s = N_{G}/N = (N-1)/N, 此刻,

1/N=1-s=e^{-\langle k\rangle s}=e^{-\langle k\rangle (N-1)/N},

两边求对数可以得到 \langle k\rangle = \ln(N), 因此,\ln(N) 也是一个临界点,并且是出现全连通图的临界点。

随机图的六度分离

六度分离又称为小世界现象,它的含义是在地球上任意选择两个人,他们之间最多相隔 6 个相识关系。换言之,来自世界上任何地方的两个人都可以通过不超过 6 个相识关系所连接起来。

The Six Degrees of Larry Stone

图中两个顶点的距离定义为两个顶点之间的最短路径长度,图的直径就是图中任意两点的距离的最大值。对于随机图 G(N,p) 而言,如果 \langle k\rangle \leq 1 则是不连通的,因此通常只需要考虑 \langle k\rangle>1 的情况,甚至只考虑 \langle k\rangle >\ln(N) 的全连通图。任取一个顶点 i,则有

  1. \langle k\rangle 个距离为 1 的顶点;
  2. \langle k\rangle^{2} 个距离为 2 的顶点;
  3. \langle k\rangle^{3} 个距离为 3 的顶点;
  4. \langle k\rangle^{d_{max}} 个距离为 d_{max} 的顶点;

同时,G(N,p) 而言,顶点的个数为 N, 这意味着 \langle k\rangle + \langle k\rangle^{2}+\cdots+\langle k\rangle^{d_{max}}\leq N. 通过等比级数的公式可以得到 \langle k\rangle^{d_{max}} \leq N, 因此,

d_{max} = O(\ln(N)/\ln(\langle k\rangle)).

而随机图的直径的量级是与 d_{max} 成正比的,因此,随机图的直径量级同样是 O(\ln(N)/\ln(\langle k\rangle)). 如果 N = 10^9 并且每个人认识 \langle k\rangle = 200 个人,于是随机图的直径量级是 \ln(6*10^9) / \ln(200) = 4.25 < 6.

参考文献

  1. Erdos Renyi Model:https://en.wikipedia.org/wiki/Erd%C5%91s%E2%80%93R%C3%A9nyi_model
  2. Giant Component:https://en.wikipedia.org/wiki/Giant_component
  3. Erdős P, Rényi A. On the evolution of random graphs[J]. Publ. Math. Inst. Hung. Acad. Sci, 1960, 5(1): 17-60.
  4. Albert R, Barabási A L. Statistical mechanics of complex networks[J]. Reviews of modern physics, 2002, 74(1): 47.
  5. 《巴拉巴西网络科学》,艾伯特-拉斯洛·巴拉巴西(Albert-LászlóBarabási),2020.

2018 年的台湾八日行

2020 年受疫情和诸多因素的影响,注定没有办法进行境外旅游了,笔者只好提笔整理之前拖欠多年的游记,回忆之前每年都外出旅游的日子。

在 2018 年端午小长假来临之际,根据国务院假日的安排,只需要请四天假期就可以得到长达 9 天的假期。端午节假期之长,总不能够留在家里一直待着。于是,笔者在 5 月底的时候就开始考虑着出去旅游。思前想后,虽然日本韩国台湾均已去过,但是台湾省还是值得多去几次,因为之前去台湾的时候都是跟团旅游,也就是传说中的“上车睡觉,下车拍照”,有些想去的地方都没有仔细地游玩。因此,这次旅游地点就再次选择了台湾。不过,要想在短短的七八天时间内把台湾整体玩一遍还是非常困难的,因为在台湾旅游适合慢慢地玩,而不适合走马观花。

台北与台中

在 2016 年和 2017 年,笔者已经跟随公司去过两次台湾,走的是完全不同的两条线路。分别是台北-台中台北-花莲-高雄两条线路,因此对台湾的大致情况也有所了解。这次是带着 RDD 一起前往台湾,于是在出行方面就全部是由笔者来设计和规划了。在出行方面,由于台北机场与香港机场的距离不远,并且从深圳到香港机场也不算特别费事,于是,笔者最终还是选择了从深圳入境香港,再从香港机场飞往台北机场。在请假的时候就把 3 天婚假和 1 天年假加在一起凑了 4 天,就获得了整整 9 天的假期。

台北 101 景色

从深圳过关到香港是相对简单的,只需要材料齐全就可以轻松过关,到达香港之后可以选择坐大巴或者做地铁前往香港机场,通常来说坐大巴会方便一些,在资金方面也可以节省不少钱。其实也可以在皇岗口岸选择坐去机场的商务车,也可以达到省时省力的目的。

在抵达香港机场之后,跟以前的一样办理登机手续和正常登机。从香港出发的时候乘坐的航班是国泰航空的 CX400,2018 年 6 月 16 日 13:10-15:10,只需要两个小时的时间就可以抵达台北桃园机场;而从台中机场返回香港的时候乘坐的是华信航空的 AE1841,2018 年 6 月 23 日 16:55-18:25。因此,从香港去台湾是非常方便和迅速的。

从行程上来安排,笔者简单地安排了以下景点:

  1. 20180616 – 20180620:台北游玩:西门町,诚品书店,宁夏夜市,中正纪念堂,中山纪念堂,士林官邸,国立故宫博物院,九份山城,平溪线,台北 101 大厦,台北松山文创园区,国立台湾师范大学等;
  2. 20180620 – 20180623:台中游玩:东海大学,静宜大学,逢甲大学(夜市),清境农场等。
国立国父纪念馆

至于从台北到台中的交通线路,可以选择在台北车站购买;而台北的交通卡叫做悠游卡,用它可以乘坐公交与地铁,同时这张卡在台北机场也有售卖点。至于手机卡等通讯设备,也完全可以等到了台湾之后再进行购买,不一定需要在国内全部准备好。由于这次的行程相对简单,只安排了台北和台中两个城市,也需要安排台北,台中两地的住宿即可。

清境农场的栈道

西门町是台北市的商业区之一,在这里聚集了无数的年轻人,而西门町距离台北车站仅仅只有 10 分钟的车程。西门町拥有各路美食,也包括各种各样的网红店。同时,西门町的诚品书店西门红楼则是来了西门町的必去之地,在这里不仅能够享受到各种美食,也能够体会到与大陆不一样的生活气息。在台北的这几天(2018 年 6 月 16 日 – 2018 年 6 月 20 日)所住的酒店是 Hotel PaPa Whale,酒店就位于西门町附近,于是无论是出行还是游玩都十分方便。

中正纪念堂是台北比较有名的景点之一,它是为了纪念蒋中正而兴建的建筑。中正纪念堂对于游客则是免费的,游客可以根据自己的时间安排来自由参观它。在大厅里面,每两个小时就会有海军仪仗队的交接仪式,只要时间安排合理游客们都有机会在大厅里面看到这场仪式。在中正纪念堂内部除了可以在四楼观看海军仪仗队的交接仪式之外,还可以在其余楼层观看其他展品。在一楼就摆设了当年蒋先生用过的一些物品,也介绍了历史上的一些故事。在中正纪念堂的外面有一个牌楼,上面写着“自由广场”四个大字。在 GOOGLE 上也可以搜到很多团体会根据日程安排在自由广场举办相应的活动,有兴趣的朋友在旅游之前不妨研究一下。

中正纪念堂

在中正纪念堂参观完了之后,不妨去附近的“金峰卤肉饭”吃一顿网红美食。从中正纪念堂到金峰卤肉饭也就几百米的路程,步行前往倒花不了多少时间,但是在排队等饭的时候却是花了许多功夫。毕竟这家餐厅的人气实在是太旺了,周边的游客都会闻风而来,每到饭点这间店的门口总是会排起长龙。

自由广场

从中正纪念堂前往台北的国立故宫博物院其实是需要花费一个小时的时间,需要从中正纪念堂乘坐捷运到士林站,再从士林站转乘巴士 255 区间车前往国立故宫博物院。不过在士林站附近有士林夜市,在游玩故宫博物院结束之后在返程途中可以前往士林夜市吃晚饭。台北故宫博物院是台湾省最大的博物馆,其著名的展品包括翠玉白菜,红烧肉,毛公鼎,象牙球等诸多文物。除此之外,在一些特殊的时期,故宫博物院也会根据需要来进行一些历史文物,名人字画的展示。这就看各位游客去的时候有没有赶上好时候了。

国立故宫博物院
翠玉白菜
红烧肉

在士林站和国立故宫博物院中间,还有另外一个景点,那就是士林官邸。它是蒋中正在台湾时期的官邸,在参观的过程中可以看到蒋中正先生当年的日常生活情况,屋子里面的装修精致大方,屋外还有一片花园,是一个可供拍照的好去处。成人的票价也十分便宜,100 新台币即可(约合人民币 23 块),游玩时间大约 1 个小时。

士林官邸

松山文创园区是台北信义商圈的一个景点,里面有不少文艺的作品和文艺的小店。诚品书店也在其中有分店。而在信义商圈附近,最著名的应该就是台北 101 大厦了,它位于台北的核心地带,在 101 上的观景台可以将台北的景色一览无余。因此推荐大家在傍晚之前登上观景台,这样的话就可以同时参观白天和晚上的景色了。在 101 附近也有国立国父纪念馆,如果有兴趣的朋友也可以抽空前往,毕竟这几个地点的路程都不算太远。

台北 101 夜景

在台北旅游除了可以参观上述景点之外,对校园生活感兴趣的朋友也可以选择去参观台湾大学台湾师范大学等著名高校。笔者第一次去台湾大学的时候是跟着公司的 2016 年团建,正好有一天属于自由活动的时间,于是约上了 PHD 的朋友在台湾大学数学研究所见面,顺便也参观了一下台湾大学的校园生活。而在台湾大学附近,也有不少文艺的咖啡厅和小店,同样吸引了不少的游客前往游玩。

九份山城

在台北除了可以参观各种著名景点之外,距离台北车站 2 个小时车程的九份山城也是来台北的游客会去参观的地方。九份山城其实已经不属于台北,而是属于新北市的瑞芳区,早期由于金矿而繁华,后期由于金矿挖尽而没落。不过近几十年由于各种各样的原因,九份山城已经被改造成一个旅游景点,吸引着不少大陆,日本和韩国的游客去游玩。在九份山城,除了可以感受到当年挖金矿的人们的日常生活之外,还可以在九份山城享受各种美食,包括芋头,烤肠,各种当季的台湾水果等。

平溪线的小火车

从台北车站去九份的话必定会经过瑞芳车站,而从瑞芳车站走平溪线也别有一番滋味。因为平溪线是区间车,因此游客可以在每个站都下来玩一下,然后到点了就乘车前往下一个车站。沿途的车站包括猴硐猫村,十分车站,平溪车站,菁桐车站等景点。每个景点可以游玩的时间大约是 1 个小时,不过这些车站都不大,一般来说不会游玩那么久的时间。而且这些车站的相似度非常高,如果没有特别的爱好,其实也没有必要每一个车站都下去玩。

平溪线的竹筒
平溪线的车站

由于这次的假期有 9 天,因此只在台北的话就略显得有点单调。于是在安排行程的时候就把台中包含了进来。从台北到台中的车程也就一个小时左右。如果说台北是台湾最繁华的城市,那么台中就显得比台北破旧一些。在台中市区内可以游玩的景点确实不算多,基本上都是在台中的周边地带。包括东海大学,静宜大学,彩虹眷村,甚至更远的清境农场与日月潭。

逢甲夜市

提到台中市的夜生活,就不得不去台中最著名的逢甲夜市。为了能够在台中享受到美食,笔者在订酒店的时候就特定选择了位于逢甲夜市的酒店 KUN Hotel。于是,在台中的这几个晚上,都在逢甲夜市吃的晚餐。逢甲夜市不仅包括各路小吃,也包括各种饮品,甚至还包括各种卖东西的商店,属于一个非常大的商圈。每逢假日,逢甲夜市总是人满为患,道路被挤得水泄不通。因此来台中的游客一定不要错过这个著名的逢甲夜市。

东海大学的路思义教堂

在台中市,除了夜市附近的逢甲大学之外,还可以去参观东海大学静宜大学。东海大学是台湾的一所私立大学,与 1963 年建成的路思义教堂则是东海大学的著名景点之一。除此之外,东海大学还有农业的相关院系,因此东海大学的牧场所出售的牛乳制品也是一绝,其中包括牛乳冰淇淋,牛奶,冰棍等。而静宜大学出名恐怕是由于电视剧《恶作剧之吻》的热播,袁湘琴与江直树在剧中的天台则成为许多游客的打卡地。

静宜大学的天台
静宜大学的音乐台
静宜大学的公告栏

南投县距离台中市区并不远,而清境农场与日月潭也是在行程之内。只是当时的天气不太好,然后就只规划了一个景点,那就是清境农场。只不过乘车抵达清境农场之后同样是下雨,逛农场的时候都只能够撑伞,也没有机会触摸到毛茸茸的绵羊。只是在小商店购买了一些羊奶制品进行享用。不过幸运的是恰好赶上了一场马戏表演,这也算是在清境农场的不错的体验。其实从台中赶到清境农场其实也要花费一定的功夫,如果想省事的话,其实可以报一个当地团前往,不仅可以游览清境农场,还可以顺便游玩一些周边的景点,包括巧克力工坊小瑞士花园等。但是对于钢铁旅游的朋友来说,就可以自行前往,并且在一天之内把日月潭和清境农场游玩一遍。

清境农场的绵羊
清境农场的花
清境农场的风车

在深圳的这几年时间里,笔者去过台湾三次,去过的地方包括台北,九份,花莲,垦丁,高雄,台中,日月潭,清境农场等诸多地方。本想着有机会的话再去慢慢地走一遍台湾的其他景点和城市,但是近些年由于种种原因则无法出行。后续会继续寻找机会再去一次台湾,让忙碌的工作尽量慢下来,慢慢去体验生活所带来的乐趣。

随笔(三)— 深圳的房价

第一次来深圳的时候应该是在 2011 年左右,作为博士生每年都有 21 天的假期,那自然是会回到家乡与家人团聚。从新加坡回大陆的话一般来说都有廉价航空(Tiger),所以为了省钱会制定一条较为折腾的路线。每次从新加坡返回家乡的时候都选择先去香港,再从香港进入深圳,最后从深圳返回贵州。笔者当时对深圳的印象也挺好,无论是从自然气候,空气环境,城市建设等方面,深圳与新加坡都是十分相似的。

在 2011 – 2012 年期间,笔者每年都会回国,会时不时地往返香港与深圳,笔者也经常拿这两座城市做比较。当时在香港居住的地方是钻石山的星河明居,附近拥有荷里活广场(Hollywood Plaza)和一些便利店,因此日常生活用品和做饭材料都可以在荷里活广场买到,整体来说生活也算方便。当时的星河明居有 A,B,C,D,E 这几栋,住的那一个屋子大约 50 平左右,有三个房间,再加上客厅的话总共有四个居住场所,所以日常的租户是 4 人。有一个房间就特别小,测量了一下大约只有 4 平左右。在居住的闲暇之余还去周边的房产中介看了一下,50 平左右的这个房子大约的价位是 550 万港币,总体来看,这些房子的均价大约是 10 万港币 / 平左右。

星河明居

从星河明居到罗湖口岸其实并不花太长的时间,从观塘线转到东铁线,再进入罗湖也就大约 1 个小时。一旦进入了罗湖,总想着也需要比较一下深圳和香港的房价,当年也在深圳的福田和罗湖浏览了一些小区的房价,当时福田不少小区的均价还在 2 万以下,在罗湖也能够找到 1 万多的小区。

星河明居楼下

当时关注的房子基本上都是小户型,毕竟即使是小户型也会远好于在星河明居只有 4 平方的房间。福田或者罗湖的一室一厅的面积都是在 20 – 40 平左右,一般来说不会到 60 平。当时关注的不少小区房价相对于香港还是便宜许多的,两者的距离仅仅相差了一个罗湖口岸。

当年关注过位于八卦岭的鹏益花园这个小区,小户型(一室一厅,小于 40 平方)的价格是有明显变化的。在 2013 年的时候,60 万人民币基本上可以拿下一套小户型,但是从链家的官网来看,房价处于一个高速上升的势头,不管是由于学区房还是其他原因,整体的房价都在提升。据不完全统计和肉眼观察,鹏益花园的房价基本上是:

  1. 2010 年大约是 10 k / 平;
  2. 2014 年大约是 20 k / 平;
  3. 2019 年大约是 50 k / 平;
  4. 2020 年大约是 90 k / 平;

除了鹏益花园之外,还有南山的诺德假日花园,同样呈现了较大的增长势头。从链家的交易记录来看,可以看到小区的交易价格大约是:

  1. 2010 年大约是 20 k / 平;
  2. 2016 年大约是 70 k / 平;
  3. 2020 年大约是 140 k / 平;

无论是鹏益花园,诺德假日花园还是深圳的其余小区。在短短的十年时间,二手房的价格大约涨了 8 – 9 倍。这对于应届生而言,如果是 2010 年来了深圳之后就迅速买房,虽说不一定能够保证财务自由,但是也足以节省一大笔钱,而且房产的资产增值幅度有很大可能已经远超工资上涨的幅度。如果是 2015 年来深圳的应届生,虽然也经历了 2015 年房价迅速增加的一段时光,但是估计也没想到有的小区在短短的 5 年之后还能够继续保持一定的涨幅,并且有些地区的涨幅基本上是翻倍了。

在 2020 年的初期,深圳的房价又一次出现了上涨的势头,整体的价格相对于 2019 年确实涨了不少。即使是从 2020 年的 8 月份算起,深圳的房价也呈现了稳中有升的局面,从价格上来看并没有出现下降的趋势。

10646元!2019年深圳市在岗职工月平均工资(即社平工资)出炉。记者分别从深圳市医疗保障局、深圳市社会保险基金管理局获悉,从7月起我市各项社保缴费基数和待遇偿付基数也随之调整,涉及到2019年全省全口径从业人员月平均工资、2019年深圳市在岗职工月平均工资的,分别按6756元、10646元/月计算。

这十年来的变化,使得深圳的二手房房价已经快追上了香港,2020 年的深圳房价已经不是 2010 年的水平了。但是其工资水平其实并没有发生那么多倍的变化,能够在早期入手购房的人说不定已经财务自由,但是对于刚来深圳的应届生而言,在深圳安家的成本就会变得越来越高,根据深圳市的调查,深圳市最新的社平工资为 10646 元。其链接是:我市最新社平工资为10646元/月 工伤发生人数下降15.28%

从深圳的平均工资和二手房均价来看,如果只是靠个人的薪水想要攒到深圳核心地段的房子首付确实是一件较难的事情,如果家里面能够提供必要的支持确实能够帮助应届生解决问题。此时,有的同事会选择在深圳打工,然后想办法供二线家乡城市的房子。毕竟无论在哪里工作,最终都是为了能够过上更好的生活。(未完待续)

随笔(二)—工作与生活

从小听过不少家长或者老师的“谎言”,读初中的时候,老师们总是说让大家努力学习,只要考上了高中就可以轻松学习了,毕竟从高中考大学是相对容易的;在高中的时候,老师们也总是说让大家继续努力学习,保持学习劲头不放松,等考上了大学就可以开始真正的素质教育了;但是到了大学的时候,才发现所谓的学习生活并不是跟高中老师所说的一样。从某种程度来看,大学教育在某些时候也是一种应试教育,跟高中的模式没有太大的区别,要想获得某门课程的好成绩同样也需要花费很多时间和精力的。

笔者在读博士的时候,在刚入学的第一年总想在很短的时间内做完某件事情,甚至在刚入学的第一个学期都没有在周边进行游玩和娱乐,也没怎么进行休息,一直在尽力地学习各种数学课程,阅读科研论文。等到了博士第二年的时候,心态就出现变化,毕竟博士生做论文并不是花费几个月就能够搞定的,科研与学习是有本质区别的。科研是一种生活状态,无论博士生在办公室,在路上,在家里,甚至在吃饭的时候,都可以思考问题,不断地考虑论文中的突破口,不停地进行各种各样的演算和尝试,在每一次的失败中寻求成功的路径。如果科研是一种生活状态,那就不太可能出现读完,写完某篇论文就不用继续努力付出的情况。对于博士生而言,科研与生活会长期并存,互相交织在一起。

其实无论是在中学,大学,研究生,还是博士阶段,甚至到了工作时期,都不太可能出现度过了某个阶段,下个阶段就无比轻松的情况。在不同的阶段都有着完全不同的任务和目标,都有着截然不同的挑战和困难。在小学,中学,大学的时候,大家还是以学生的身份而存在;到了研究生,博士阶段的时候,大家就要考虑未来的生计问题了;等到了工作期间,大家考虑和谈论的事情基本上就是事业,成家,立业等家庭问题;到了生儿育女的阶段,大家商讨的应该就是学区房,小孩成绩等诸多问题了。因此,无论在人生的哪个阶段,并不会出现丝毫没有任何压力的情况,也很难出现一个阶段过去了下一个阶段就很轻松的事情,说不定下一个阶段比上一个阶段更加的艰难。

在人的一生中,学习,工作,生活三者将会一直共存,进入工作阶段并不意味着学习的停滞,在学习期间也不意味着不需要生活,在工作阶段更不意味着可以永远不休息。生活和工作在每个人的人生中其实是不可严重割裂的两块,对大多数人而言,是很难做到不需要工作而只需要生活的,也很难做到不需要生活而只需要工作。当然,在某个短暂的阶段我们完全可以做到放弃其中的某一样而努力做到另外一件事情,但是以长远的眼光来看,工作与生活其实是长期并存的关系。

在一线城市工作,虽然日常会承受 995 甚至 996 的工作压力,但是总还是可以找到休息的机会。不过据说有的公司是 007 的工作状态,那么估计这些员工是没有生活了。但是 007 的工作状态也不会持续一辈子,毕竟人的体力和精力都是有限的,在某个合适的时刻这种工作状态会被改变的。如果不想拥有高强度的工作压力,就要合理地降低自身的欲望。如果想在职场发展中持续地赚到钱或者维持高收入,就必然要保持自身的竞争力。而竞争力的来源包括工作时长,技术能力,管理能力等诸多方面,其中工作时长是最容易体现竞争力的一个方面,这也许正是 996 的由来。但即使是高强度的工作,也可以尝试在工作间隙进行必要的休息和生活,例如午饭和晚饭的时间。工作人士可以在这两个时间段做一些自己喜欢的事情,体验一下与工作完全不同的生活。

工作在某些时候就跟读博士一样,千万不能够想着读完了博士就怎么怎么样,而是要学会把大任务拆解,安排好每个时间段的工作。只要每天,每周,每月,每年做完一定的任务之后就及时享受生活和体验人生。只有这样才能够保证自身的能量充足,能够长期在工作中保持战斗力。工作是人生的必经阶段,也是日常生活的一部分,为了更好地生活,我们需要努力的工作,但是并不需要为了工作而放弃所有的生活。

在工作的时候,通常任务有日常的常规任务,也有充满挑战的创新性任务。在做常规任务的时候,可以搞一些可以提升效率的工具,减少重复工作的时间。在做创新性项目的时候,就要一往无前地全力以赴,毕竟创新性的工作除了给人带来工资与收益之外,还能够给人带来巨大的成长,为今后的工作做必要的铺垫。只做重复性的工作很容易让人产生疲惫的心理,在互联网这种充满风险和挑战的地方还是要做一些对自己有提升的工作。一旦目前的工作都已经手到擒来,没有任何挑战,那就可以考虑去找一些更有挑战的项目来提升自己了。

工作与生活是不能被分割的两部分,很难放弃其中的一个而只选择另外一个。在日常的工作中,通过项目来精进自身的能力,在工作中获得一定的成就感。在生活中及时地享受人生,在娱乐之余及时地给予自己一定的奖励,只有这样,才能够更好地平衡工作与生活。

随笔(一)— 养娃一月记

对于一线大城市的年轻人而言,读书,就业,买房,恋爱,结婚,生娃都是非常重要的事情。但对于不同的人却有着不一样的顺序,也许结婚的时候并不在当时工作的城市,或者在某个阶段就早已回到家乡重新开始新的生活。不过这些事情对于年轻人以及背后的家庭而言,都是一个又一个的里程碑(Milestone),是一段新生活的开始。

从今年七月份开始,笔者的日常生活基本就是围绕着小朋友而展开,从一开始进医院陪产,出院之后直接进入月子中心,到离开月子中心重新回归家庭,直到最后家里迎来了新的成员。

说到生产的医院,就是在怀孕的初期或者中期就需要确定下来。而在建档的时候父母双方可以在市里的妇幼保健院建档,当场录入父母双方的信息以及基本情况。此时妇幼保健院还会要求父母做一些必要的检查,例如地中海贫血症等,也会查一下父母双方的血型,以便后续有需要的时候会作进一步地检查。

在妇幼保健院建档并不意味着只能够在妇幼保健院生宝宝,也可以在中途更换到其他的医院,此时完全可以考虑根据自身和家庭的情况选择最适合的方案。有的医院床位紧张,可能到时候产妇和家属需要睡在楼道里面;有的医院床位宽松,产妇可以住在病房里面,家属则可以铺一张行军床;当然,如果家庭条件再好一点的话,去条件更好的医院,家属其实也不用铺行军床了。

在建档之后笔者选择的是香港大学深圳医院(在这里没有打广告的意思),当时去医院看了之后发现整体环境还不错,而且港大医院是预约制的,要想在港大医院生产必须预约成功才行。对医院而言,病人数量会相对可控一些,笔者去的时候也暂时没发现有产妇孕妇睡在走廊的情况。在港大医院里面有全家(MyFamily)便利店 24 小时营业,里面除了出售日常的食品和消耗品之外,还出售病人常用的一些装备,甚至还有宝宝所需要的纸尿裤,这样也极大地方便了来医院就诊的患者。港大医院的产科位于住院部 A 栋,分为东区和西区,其中东区是负责产前,西区负责产后。这样也有利于产妇的休息和宝宝的照顾。而产房则是位于门诊医技楼,因此在生产的时候,妈妈们是要用轮椅被护士推送到产房,而爸爸们则只能够在产房的大厅里耐心地等候。

香港大学深圳医院

产妇在医院的时间一般来说不会太长,通常一周左右就会正常出院,而出院了之后去月子中心还是请月嫂照顾,或者全程由家人照顾则是根据每个家庭自身情况来定的。通常来说,月子中心可以提供一系列的关于妈妈和宝宝的解决方案。月嫂的话虽然也能够帮忙和解决问题,但是一个人照顾毕竟人力有限,有的时候会出现人力紧张的情况。而全程由家人照顾的话,则需要家人懂一些育儿的经验和法则,最好家人最好还要与时俱进,不能够拿着三十年前的经验在持续使用。

今年正好处于疫情防控期间,很多医院都只能够让一个陪护人员进入病房照顾病人,基本上在病房里面不会出现一大家人进去的情况。因此对于新手爸妈而言,尤其是对爸爸来说,在医院期间同时照顾妈妈和小孩就是一件非常有挑战的事情,而这件有挑战的事情在疫情期间是没有办法让别人来帮忙的。至于月子中心或者月嫂基本上都是出院了之后才会使用,在医院只能够依赖爸爸来解决问题。

全家的冰淇淋

有的月子中心整体感觉还不错,能够针对妈妈和小孩的情况来制定相应的解决方案。毕竟对于新手爸爸来说,照顾妈妈和小孩的经验是十分缺乏的。同时对于长辈而言,很可能都是过时的经验,而且现在照顾小孩也有很多与时俱进的策略和照顾方案。况且长辈也近三十年没有带过小孩,并且带小孩也是一个体力活,不是所有长辈都能够承受这种劳动强度。这种时候如果有一个靠谱的月子中心或者月嫂,确实能够极大地减缓新手爸爸和其他家庭成员的劳动强度。

在一个靠谱的月子中心,会有很多角色与某个家庭对接,而要解决某个问题只需要找到相应的角色就可以了。通常来说会包括护士,医生,瑜伽老师,生活助理,营养师等角色,而这些角色每天负责的内容是不一样的,护士也是轮班的工作模式,会保证这些工作人员得到必要的休息。而月嫂的工作模式基本上是一个人在工作,一个人会负责妈妈和宝宝的方方面面。这种情况下,在某些时候就难免分身乏术,毕竟同时照顾两个人其实是有一定的难度和挑战的。月嫂毕竟是一个人,每天也是需要一定的时间进行休息的,这与月子中心那种随叫随到的模式是不太一样的。

月子中心

在一线城市工作,其工作节奏还是相对较快,无论是在大公司还是中小型公司,工作人士基本上都是需要加班的。这就表示爸爸即使能够照顾家里面,也仅仅局限于陪产假的期间,其他时间都是较难照顾到家里面。因此无论让长辈过来或者去月子中心,还是请月嫂都是解决问题的方法。一般情况下月子中心在深圳的价格是 26 天 5 万以上,如果需要住更长的时间或者有其他的需求,则需要更高的费用,这种时候一般都会超越 10 万人民币。同时,月子中心也会有其他的项目,包括给宝宝拍照,妈妈的瑜伽恢复和产后恢复等诸多项目,而这些项目一旦超过了前期的套餐费用,都是需要付费的,因此,在月子中心里面多花几千块或者几万块钱都是属于正常的。当然,也有一些人就做完正常的项目就没有继续做额外的项目了。

而宝宝一天的流程除了日常的喂奶,换尿布之外,还会有洗澡,抚触,早教,游泳等诸多项目。妈妈的项目除了喂奶,吃饭,还有产后修复等内容,这些项目在月子中心是由不同的角色完成的,但如果是月嫂的话则是全部由一个人完成。如果月嫂靠谱的话还算比较好,毕竟在价格方面相对月子中心还是便宜许多。其实去一次月子中心的钱其实可以请好几个月嫂了,还是要根据自身家里的情况来决定怎么做,毕竟这个对每一家而言真的是个性化的需求。

不同的家庭的确需要根据自身情况来决定该怎么做,但是有的时候自己或者家人千万不要高估自己的能力,毕竟带婴儿也是一个力气活,而且带婴儿的知识是需要不停地更新的,不学习任何知识就想带好婴儿是不可能的事情。除非一开始就打算随便养一下,那确实也没啥必要学;一旦想要好好带的话,最好还是多学习各种知识,包括母婴的基础知识,常见的育儿百科等等。整个流程还是很长,但其实这只是一个开始,后续还有更长的路需要走。(未完待续)

主动学习(active Learning)

主动学习背景介绍

机器学习的研究领域包括有监督学习(Supervised Learning)无监督学习(Unsupervised Learning)半监督学习(Semi-supervised Learning)强化学习(Reinforcement Learning)等诸多内容。针对有监督学习和半监督学习,都需要一定数量的标注数据,也就是说在训练模型的时候,全部或者部分数据需要带上相应的标签才能进行模型的训练。但是在实际的业务场景或者生产环境中,工作人员获得样本的成本其实是不低的,甚至在某些时候是相对较高的,那么如何通过较少成本来获得较大价值的标注数据,进一步地提升算法的效果就是值得思考的问题了。

机器学习

在工业界的图像标注领域,虽然有 ImageNet 这个学术界和工业界都在使用的图像数据库,但是在很多特殊的业务场景上,从业人员依旧需要想尽办法去获取业务标注数据。在安全风控领域,黑产用户相对于正常用户是偏少的,因此,如何通过极少的黑产用户来建立模型则是值得思考的问题之一。在业务运维领域,服务器,app 的故障时间相对于正常运行的时间也是偏少的,必然会出现样本不均衡的情况。因此,在这些业务领域,要想获得样本和构建模型,就必须要通过人力的参与。那么如何通过一些机器学习算法来降低人工标注的成本就是从业者需要关注的问题了。毕竟需要标注 100 个样本和需要标注成千上万的样本所需要的人力物力是截然不同的。

在学术界,同样有学者在关注这方面的问题,学者们通过一些技术手段或者数学方法来降低人们标注的成本,学者们把这个方向称之为主动学习(Active Learning)。在整个机器学习建模的过程中有人工参与的部分和环节,并且通过机器学习方法筛选出合适的候选集给人工标注的过程。主动学习(Active Learning)的大致思路就是:通过机器学习的方法获取到那些比较“难”分类的样本数据,让人工再次确认和审核,然后将人工标注得到的数据再次使用有监督学习模型或者半监督学习模型进行训练,逐步提升模型的效果,将人工经验融入机器学习的模型中。

在没有使用主动学习(Active Learning)的时候,通常来说系统会从样本中随机选择或者使用一些人工规则的方法来提供待标记的样本供人工进行标记。这样虽然也能够带来一定的效果提升,但是其标注成本总是相对大的。

用一个例子来比喻,一个高中生通过做高考的模拟试题以希望提升自己的考试成绩,那么在做题的过程中就有几种选择。一种是随机地从历年高考和模拟试卷中随机选择一批题目来做,以此来提升考试成绩。但是这样做的话所需要的时间也比较长,针对性也不够强;另一种方法是每个学生建立自己的错题本,用来记录自己容易做错的习题,反复地巩固自己做错的题目,通过多次复习自己做错的题目来巩固自己的易错知识点,逐步提升自己的考试成绩。其主动学习的思路就是选择一批容易被错分的样本数据,让人工进行标注,再让机器学习模型训练的过程。

那么主动学习(Active Learning)的整体思路究竟是怎样的呢?在机器学习的建模过程中,通常包括样本选择,模型训练,模型预测,模型更新这几个步骤。在主动学习这个领域则需要把标注候选集提取和人工标注这两个步骤加入整体流程,也就是:

  1. 机器学习模型:包括机器学习模型的训练和预测两部分;
  2. 待标注的数据候选集提取:依赖主动学习中的查询函数(Query Function);
  3. 人工标注:专家经验或者业务经验的提炼;
  4. 获得候选集的标注数据:获得更有价值的样本数据;
  5. 机器学习模型的更新:通过增量学习或者重新学习的方式更新模型,从而将人工标注的数据融入机器学习模型中,提升模型效果。
主动学习的流程

通过这种循环往复的方法,就可以达到人工调优模型的结果。其应用的领域包括:

  1. 个性化的垃圾邮件,短信,内容分类:包括营销短信,订阅邮件,垃圾短信和邮件等等;
  2. 异常检测:包括但不限于安全数据异常检测,黑产账户识别,时间序列异常检测等等。

主动学习的模型分类包括两种,第一种是流式的主动学习(Sequential Active Learning),第二种是离线批量的主动学习(Pool-based Active Learning)。在不同的场景下,业务人员可以选择不同的方案来执行。

主动学习的三种场景

而查询策略(Query Strategy Frameworks)就是主动学习的核心之处,通常可以选择以下几种查询策略:

  1. 不确定性采样的查询(Uncertainty Sampling);
  2. 基于委员会的查询(Query-By-Committee);
  3. 基于模型变化期望的查询(Expected Model Change);
  4. 基于误差减少的查询(Expected Error Reduction);
  5. 基于方差减少的查询(Variance Reduction);
  6. 基于密度权重的查询(Density-Weighted Methods)。

不确定性采样(Uncertainty Sampling)

顾名思义,不确定性采样的查询方法就是将模型中难以区分的样本数据提取出来,提供给业务专家或者标注人员进行标注,从而达到以较快速度提升算法效果的能力。而不确定性采样方法的关键就是如何描述样本或者数据的不确定性,通常有以下几种思路:

  1. 置信度最低(Least Confident);
  2. 边缘采样(Margin Sampling);
  3. 熵方法(Entropy);

Least Confident

对于二分类或者多分类的模型,通常它们都能够对每一个数据进行打分,判断它究竟更像哪一类。例如,在二分类的场景下,有两个数据分别被某一个分类器预测,其对两个类别的预测概率分别是:(0.9,0.1) 和 (0.51, 0.49)。在此情况下,第一个数据被判定为第一类的概率是 0.9,第二个数据被判定为第一类的概率是 0.51,于是第二个数据明显更“难”被区分,因此更有被继续标注的价值。所谓 Least Confident 方法就是选择那些最大概率最小的样本进行标注,用数学公式描述就是:

x_{LC}^{*}=argmax_{x}(1-P_{\theta}(\hat{y}|x))=argmin_{x}P_{\theta}(\hat{y}|x),

其中 \hat{y}=argmax_{y}P_{\theta}(y|x),这里的 \theta 表示一个已经训练好的机器学习模型参数集合。\hat{y} 对于 x 而言是模型预测概率最大的类别。Least Confident 方法考虑那些模型预测概率最大但是可信度较低的样本数据。

Margin Sampling

边缘采样(margin sampling)指的是选择那些极容易被判定成两类的样本数据,或者说这些数据被判定成两类的概率相差不大。边缘采样就是选择模型预测最大和第二大的概率差值最小的样本,用数学公式来描述就是:

x_{M}^{*}=argmin_{x}(P_{\theta}(\hat{y}_{1}|x)-P_{\theta}(\hat{y}_{2}|x)),

其中 \hat{y}_{1}\hat{y}_{2} 分别表示对于 x 而言,模型预测为最大可能类和第二大可能类。

特别地,如果针对二分类问题,least confident 和 margin sampling 其实是等价的。

Entropy

在数学中,可以使用熵(Entropy)来衡量一个系统的不确定性,熵越大表示系统的不确定性越大,熵越小表示系统的不确定性越小。因此,在二分类或者多分类的场景下,可以选择那些熵比较大的样本数据作为待定标注数据。用数学公式表示就是:

x_{H}^{*}=argmax_{x}-\sum_{i}P_{\theta}(y_{i}|x)\cdot \ln P_{\theta}(y_{i}|x),

相较于 least confident 和 margin sample 而言,entropy 的方法考虑了该模型对某个 x 的所有类别判定结果。而 least confident 只考虑了最大的概率,margin sample 考虑了最大的和次大的两个概率。

不确定性采样的差异性

基于委员会的查询(Query-By-Committee)

除了考虑单个模型的不确定性采样方法之外,还可以考虑多个模型的场景,这就是类似集成学习的方法。通过多个模型投票的模式,来选择出那些较“难”区分的样本数据。在 QBC(Query-By-Committee)的技术方案中,可以假设有 C 个模型,其参数分别是 \{\theta^{(1)},\cdots,\theta^{(C)}\},并且这些模型都是通过数据集 \mathcal{L} 的训练得到的。

如果不需要考虑每个模型的检测效果,其实可以考虑类似不确定性采样中的 least confident 和 margin sampling 方法。可以选择某一个分类器难以区分的样本数据,也可以选择其中两三个分类器难以区分的数据。但是如果要考虑所有模型的分类效果的时候,则还是需要熵(Entropy)或者 KL 散度等指标。因此,QBC 通常也包括两种方法:

  1. 投票熵(Vote Entropy):选择这些模型都无法区分的样本数据;
  2. 平均 KL 散度(Average Kullback-Leibler Divergence):选择 KL 散度较大的样本数据。

投票熵(Vote Entropy)

对于这种多模型 \{\theta^{(1)},\cdots,\theta^{(C)}\} 的场景而言,可以用熵来衡量样本数据被这些分类器区分的难易程度,如果这些分类器都把样本数据划分到某一类,则容易区分;如果分类器把样本数据划分到多类,则表示难以区分,需要重点关注。用数学公式表达就是:

x_{VE}^{*}=argmax_{x}-\sum_{i}\frac{V(y_{i})}{C}\cdot\ln\frac{V(y_{i})}{C},

其中 y_{i} 表示第 i 类,求和符号表示将所有的类别 i 相加,V(y_{i}) 表示投票给 y_{i} 的分类器个数,C 表示分类器的总数,并且 \sum_{i}V(y_{i})=C

平均 KL 散度(Average KL Divergence)

KL 散度可以衡量两个概率之间的“距离”,因此可以用 KL 散度计算出那些偏差较大的数据样本。用数学公式来描述就是:

x_{KL}^{*}=argmax_{x}\frac{1}{C}\sum_{c=1}^{C}D(P_{\theta^{(c)}}||P_{\mathcal{C}}),

其中 P_{\mathcal{C}}(y_{i}|x)=\frac{1}{C}\sum_{c=1}^{C}P_{\theta^{(c)}}(y_{i}|x) 也是概率分布,D(P_{\theta^{(c)}}||P_{\mathcal{C}}) 表示两个概率的 KL 散度。

期望模型变化(Expected Model Change)

模型变化最大其实可以选择那些使得梯度变化最大的样本数据。

期望误差减少(Expected Error Reduction)

可以选择那些通过增加一个样本就使得 loss 函数减少最多的样本数据。

方差减少(Variance Reduction)

选择那些方差减少最多的样本数据。

基于密度权重的选择方法(Density-Weighted Methods)

有的时候,某个数据点可能是异常点或者与大多数数据偏差较大,不太适合做样本选择或者区分,某些时候考虑那些稠密的,难以区分的数据反而价值更大。于是,可以在使用不确定性采样或者 QBC 方法的时候,将样本数据的稠密性考虑进去。用数学公式表示就是:

x_{ID}^{*}=argmax_{x}\phi_{A}(x)\cdot\bigg(\frac{1}{U}\sum_{u=1}^{U}sim(x,x^{(u)})\bigg)^{\beta},

在这里,\phi_{A} 表示某个不确定性采样方法或者 QBC 方法,\beta 表示指数参数,x^{(u)} 表示第 u 类的代表元,U 表示类别的个数。加上权重表示会选择那些与代表元相似度较高的元素作为标注候选集。

B 附近的点信息量会大于 A 附近的点

总结

在主动学习(Active Learning)领域,其关键在于如何选择出合适的标注候选集给人工进行标注,而选择的方法就是所谓的查询策略(Query Stategy)。查询策略基本上可以基于单个机器学习模型,也可以基于多个机器学习模型,在实际使用的时候可以根据情况来决定。整体来看,主动学习都是为了降低标注成本,迅速提升模型效果而存在的。主动学习的应用场景广泛,包括图像识别,自然语言处理,安全风控,时间序列异常检测等诸多领域。后续笔者将会持续关注这一领域的发展并撰写相关文档。

参考资料

  1. Settles, Burr. Active learning literature survey. University of Wisconsin-Madison Department of Computer Sciences, 2009.
  2. Aggarwal, Charu C., et al. “Active learning: A survey.” Data Classification: Algorithms and Applications. CRC Press, 2014. 571-605.

软技能 2:软件开发者职业生涯指南

《软技能 2:软件开发者职业生涯指南》的作者是【美】John Sonmez,他是畅销书《软技能:代码之外的生存指南》的作者,也是 “Simple Programmer” 网站的作者。他为在线培训机构 Plural sight 开发了 50 多门在线课程,涉及 iOS,Android,.NET,Java 和游戏开发等多个主题。他是 “Get Up and Code” 播客的主持人,在这里他讨论 “程序员健身”;他还是 “Entreprogrammers” 播客的主持人,在这里他和其他三位开发者/企业家分享他们构建在线业务的真实故事。

软技能 2

之前笔者也撰写过一篇关于《软技能:代码之外的生存指南》的简单介绍,在第一本书中,作者撰写了职业,自我营销,学习,生产力,理财,健身,精神等七个章节。而在第二本书中,作者的侧重点就放在以下五个方面:

  1. 如何转行成为软件开发者:介绍了入行经验,傍身之技,如何学好一门编程语言等部分;
  2. 找到一份工作:初出茅庐,创新思维,唇枪舌剑等部分;
  3. 关于软件开发你需要知道什么:编程语言概述,开发流程,测试流程,代码维护等部分;
  4. 软件开发者的日常工作:与同事,老板,质量保障人员,生活,团队的共存,协作之道等部分;
  5. 推进你的职业发展:建立声望,广结善缘,与时俱进,笔耕不缀,未雨绸缪,学无止境等部分。

从本书的标题《软技能 2:软件开发者职业生涯指南》就可以看出这本书将会关注程序员的职业生涯发展,与第一本书《软技能:代码之外的生存指南》略有不同。而从章节的安排来说,作者依次介绍了转行,求职,软件开发的日常工作,职业发展路径的部分。

本书的阅读对象主要包括 3 类:

  1. 初学者或者只是对学习软件开发感兴趣的人士;
  2. 中级开发者;
  3. 神经百战的专业人士。

从豆瓣的评分来看,《软技能 2:软件开发者职业生涯指南》的评分高达 9.0,当然这个要经过时间的考验才行。

豆瓣评分

笔者拿到《软技能 2:软件开发者职业生涯指南》这本书没多久,还没来得及读完所有的章节,只好选择部分章节来摘选一下该书中的经典语录:

第四篇:软件开发者的日常工作

你要是想通过获得越来越多的职责来成长和扩展你的领地,就找一些还没有人探索过的沼泽地,没有人想去碰它,你把它拿走,别怕它会弄脏你的手,然后在那里建造出一个主题公园—华特.迪士尼就是那么做的。找出那些没人愿意染指的领域,那些没人愿意触碰的项目,接管它们。然后,让它们变成你的高光时刻。我向你保证,如果你能持续得到晋升,并在任何组织中加大你的职责,最后加薪的事情将不在话下。

你能做的第一件事情就是投资对自己的教育。坦诚地讲,你要买更多的书并阅读它们。只是读书还远远不够,还要聆听在线课程,并且真正完成它们。走出去参加研讨会或者行业会议,以及现场培训课程。

第五篇:推进你的职业发展

只有习惯性地做比被要求更多的事情,才能够带来进步。— 加里.瑞安.布莱尔

如果你真的想要出类拔萃,你真的想要把你的事业提升到一个更高的水平,你就需要学会如何建立起稳固的声望,包括如何推销自己,如何打造个人品牌,这些将为你打开常人难以企及的机会之门。

下面列出的是可以让你出名的渠道或者方法:

1. 写出你的博客;

2. 在其他人的博客发表评论;

3. 写一本书;

4. 为杂志撰写文章;

5. 登录别人的播客;

6. 创建自己的播客;

7. 创建自己的 YouTube 频道;

8. 成为一名活跃的 Twitter 或者其他社交媒体用户;

9. 在当地的用户组和编程训练营上发表演讲;

10. 在大型开发者人员会议上发表演讲;

11. 创建一个广受欢迎的开源项目。

我发现,在编程的世界保持与时俱进的最佳方法之一就是每天清晨花 30 分钟左右的时间阅读编程方面的博客。

你需要持续不断地学习新东西。不管你对当前的技能是多么驾轻就熟,也不管你的教育背景有多么深厚博大,你总是要去学习新东西。定期评估你现在的技能,定期校正你的学习方向,这样就可以明确确定你应该学习哪些新东西,以及你的学习内容的优先级和顺序。不过,要注意一点:不要去学那些你永远都不会用到的东西。

无论你眼下的工作岗位或者工作氛围多有保障,都不要过得太安逸,这点很重要。

行家里手:做专才还是做通才?真正的答案应该是:两者兼而有之。如果在你的领域内没有对综合知识的广泛积累作为基础,那么想成为一名优秀的专家是非常难的。当公司说他们想要一个通才的时候,他们真正说的是:他们想要的是一个适应能力强,学习速度快的人。他们担心的是他们会雇佣一个只能做一件事情的人。宁可错误地选择过于狭小,太过具体的专业方向,也不要选择太宽泛。你要么在自己选定的主攻方向上直接深入地透彻研究,要么就去学习那些放之四海而皆准的永恒经典。不要试图学习一堆你可能永远不会用到的编程语言与框架。

一般来说,你会发现,软件开发者不管选择了那一条特定的职业路径(也许不止一条),最终都会遇到所谓的“玻璃天花板”。这个玻璃天花板实质上就是一个极限,限制了你在职业发展路径上可以前进多远,限制了你作为一个软件开发者可以得到的最高薪酬。无论你决定做什么,最重要的是:你需要做出决策,并且为此做出计划。

结束语

知道要做什么与知道该怎样付诸实践之间,还存在着巨大的鸿沟。

就在今天,就在此刻,立即采取行动!

深圳坪山行

坪山区是深圳东北部的一个市辖区,它的东部是惠州,南部是大鹏新区。随着坪山高铁站的投入使用,从坪山高铁站到深圳北站只需要 20 分钟的时间,从坪山高铁站到福田站也仅需 50 分钟。虽然坪山距离福田的距离也没有那么远,通过高铁也可以极大地缩短了从坪山到深圳关内的时间,但是笔者来深圳近五年时间由于种种原因也没有去过坪山区。

深圳市行政区域划分

近日由坪山区人才局的领导牵头,也有 NUS 的校友牵线,笔者有幸于 2020 年 7 月 12 日参加了“新加坡国立大学及南洋理工大学博士坪山行”的活动。该活动是希望大家能够进一步地熟悉坪山,了解坪山产业企业的真实情况,参观坪山的文化聚落,以及与各个领导和部分企业进行深入交流。

虽然从福田到坪山有高铁可以前往,但是这次活动的举办方还是贴心地从福田区的市民中心安排了大巴,让大家可以选择乘坐大巴或者自行驾车前往坪山。在这个行程活动中,包括几个关键的环节:

  1. 【08:45】从市民中心 B 出站口出发前往坪山;
  2. 【10:30】参观坪山国家生物产业基地— 生物医药园区企业;
  3. 【12:00】区政府食堂;
  4. 【13:40】参观坪山文化聚落;
  5. 【15:00】与坪山的各位领导和部分企业进行交流;
  6. 【18:00】返程。
深圳国家生物产业基地

从福田到坪山的路上,只要进入坪山区,在街道两侧就可以见到不少的生物医药公司。而深圳的国家生物产业基地也正是位于坪山,坪山也将生物医药产业当做重点发展的方向之一。

生物产业基地

从地图上可以看到,随着未来的深圳地铁 14 号线投入运营,坪山与福田的距离将会进一步拉近。而在 14 号线周围则有很多的生物医药公司,医疗器械公司等高科技企业,也吸引了不少生物专业和医疗方向的工作人员前来工作。

生物产业基地的发展历程

坪山的三大重点产业包括生物医药,新一代信息技术,新能源汽车产业。生物医药包括高端医疗器械,生物制药,基因诊断,生物医药工程,现代中药,化学制药,医疗器械等产业;新一代信息技术包括人工智能,新型显示,高端设备等产业;新能源汽车包括技术创新,关键材料及核心零部件,高端整车等领域。

规划模型示意图

从展厅中的规划模型中也可以看到,除了相关的企业提供就业岗位之外,也有人才保障房,文化聚落,公园等周边设施,进一步地完善了人们的日常生活需要。

坪山区的人才引进计划

创办企业自然离不开人才,除了一些保障房的建设,坪山区还启动了“聚龙引才”工程来推动人才汇聚坪山。“聚龙英才”需要围绕坪山区的重点产业,包括深圳市认定的 A,B,C 类人才都在补助的范围内。其中 C 类人才还包括 5 年 200 万元奖补和任内免租金 100 平人才房。坪山区的重点产业包括新能源(汽车),生物医药,新一代信息技术。也支持“聚龙英才”的创业创新团队去坪山发展。除此之外,还包括“聚龙名师”,“聚龙名医”等诸多优秀的人才项目。

坪山图书馆

大家书房

坪山文化聚落是坪山区大力建设的重大文化设施,包括剧场,美术馆,展览馆,文化馆,图书馆,书城等多种文化功能,是一个综合建筑群体。图书馆除了提供日常的读书,借阅书籍等功能之外,还有一个“大家书房”,在今年年初的时候有不少的名家学者会来到坪山图书馆给市民带来人生哲思课。

商品房

在坪山的文化聚落附近,周边设施也日渐完善,不仅包括超市,银行,快餐店,还包括坪山实验学校,坪山区中心公园。人们除了工作之外,日常生活和居家氛围也能够得到必要的保障。

公园

本次的​“新加坡国立大学及南洋理工大学博士坪山行”不仅让大家认识了坪山的产业布局,也了解了坪山的人才计划,还知晓了坪山的文化聚落。希望以后还有机会能够进一步地来熟悉坪山,最后也感谢大家对这次活动的组织和筹备工作。

在新加坡的这五年—生活篇(六)

校庆对于每所大学都是非常重要的一件事情,它不仅标志着大学的诞生,也可以反映学校的发展历史。今年正值新加坡国立大学成立 115 周年,也是笔者毕业五周年之际,于是提笔写下此文回忆当年参加毕业典礼的往事。

新加坡国立大学

新加坡国立大学(National University of Singapore,简写为 NUS)是新加坡的第一所高等学府,是亚洲的顶级名校,其前身是一所成立于 1905 年的海峡殖民地医学学校,距今已经有 115 年的历史。目前,新加坡国立大学已经是拥有多个学院的综合性研究大学,其中包括理学院,工学院,商学院,医学院等重要学院。在泰晤士报的排名和 QS 世界大学排名上,NUS 一直在亚洲甚至世界上名列前茅。

NUS 的官网

在 NUS 的官网上,也换成了 115 校庆的页面,同时右上角的标语 “SHAPING THE FUTURE” 引入眼帘。其标语的中文含义大致就是形塑未来。并且可以在 NUS 的官网上看到校长寄语。

校长寄语

其大致的中文意思就是:

打开时光的卷轴,走进新加坡国立大学的峥嵘岁月,重温那些为国家为社会作出的卓著贡献。这一刻,我们深受鼓舞,我们倍感振奋!百余年间,新国大的优秀传统和创新精神一路引领着我们,追求卓越,精益求精,不断取得新的成就。

近年来,我们不断提升教学质量,增强科研能力,探索创业培育,构建一流的教育管理体系。未来我们将继续提供高质量的变革性教育,开展前沿和具有实际应用的科学研究,发扬传承创新精神,建设一个更美好的新加坡和世界。

新加坡国立大学始终致力于塑造未来。欢迎你与我们一起秉承新国大的创新精神,共同实现新国大立志成为全球最具创新力大学之一的愿望。

——陈永财教授

新加坡国立大学校长

NUS 的里程碑

除此之外,在 NUS 的 115 周年的官网上也可以看到近些年来 NUS 在科学研究和教育领域所取得的成绩和里程碑。无论是 Technology(科技),Health(健康),Enterprise(企业),Community(社区),Sustainability(可持续发展)方面,新加坡国立大学都取得了非常不错的成绩。

NUS 2020 年的毕业典礼

由于今年的新冠病毒猖獗,3 月份的 NUS Open Day 也从线下转成了线上,开启了史上第一次的 NUS E-Open House。在 2020 年的 5 月份至 6 月份,新加坡也开启了封城的策略,鼓励民众戴口罩少出行。往年的 7 月份,都是学生们参加毕业典礼的时候。但是今年为了防控疫情的需要,毕业典礼将会从 2020 年 7 月份延期至 2021 年的 1 月份延期半年,具体时间等待通知。

NUS 2015 年的毕业典礼

当年笔者是在 2015 年从 新加坡国立大学毕业的,当年毕业的时候学生签证恰好到期,最终还是通过办理旅游签证的方式进入新加坡。当时的毕业典礼是在 University Cultural Centre 举行,时间跨度从 2015 年 7 月 6 日 – 24 日。每个学生参加毕业典礼的时间是根据学位,院系等情况来进行安排的,有可能被安排在早上,下午,或者晚上。

2015 年的小狮子

在参加毕业典礼的时候,学生们都必须穿上相应的衣服,然后上台领取学位证书和成绩单。在 Universal Cultural Centre 外面,会有各种各样的道具以供毕业生们拍照。

NUS 百年校庆纪念邮票

在 2005 年,恰好是新加坡国立大学百年校庆的日子,其百年校庆的口号是 Unleashing Minds, Transforming Lives(思想任驰骋,生活显姿彩)。为了庆祝百年校庆,新加坡国立大学和新加坡邮政(Singapore Post)在 2005 年 4 月 20 日联合发行了纪念邮票。不过,当年的笔者才刚刚进入大学,从来没有想过会在五年之后进入 NUS 攻读博士学位,有的时候人生总是那么的奇妙。

毕业典礼结束

在参加毕业典礼的时候,学生需要穿着学位服,而学位服的获得方式有两种,一是通过购买的方式,二是通过租赁的方式。每个学生参加毕业典礼的时候,都会获得两张门票,也就是说可以带自己的亲戚朋友去参加毕业典礼。学校的礼堂分两层,毕业的学生需要穿着相应的毕业服坐在第一层,然后在轮到自己的时候上台领取毕业证,再返回自己的位置。而自己的亲戚朋友可以坐在二楼,从高处观看所有的学生参加毕业典礼。而颁发毕业证的时候,都是校长亲自颁发,一般情况下这是普通学生能够接触到校长的唯一机会。

博士毕业照(从左到右:赵博士,王博士,郦博士,蔡博士,徐博士,张博士)

笔者当年参加毕业典礼的时候是 2015 年 7 月 9 日,当天下午就与众多博士生一起在 NUS 的校园里面合影留念,毕竟博士毕业是人生的一件大事。上图都是当年在 NUS 已经取得博士学位的同学们,里面绝大部分已经走向了学术科研的道路,只有少数人投身进入了工业界。

毕业典礼日程表
与校长近距离接触

当时笔者在参加毕业典礼的时候,拿到一张毕业典礼的日程安排,时间是在 2015 年 7 月 9 日的晚上 8:00 开始,其中包括领导讲话,优秀毕业生致辞,颁发学位证书等环节。到了颁发学位证书,需要学生们上台的时候,学生们要先在旁边按照既定顺序站好,然后逐一上台领取毕业证并且与校长合影。而在每个学生领取毕业证书的时候,屏幕上都会呈现出文凭的名称和学生的名字。

白天的 S17 天桥
晚上的 S17 天桥

新加坡是一个降雨非常频繁的国家,第一年在 Science Library 学习的时候,大约在 11,12 月份雨季,每天到了下午 4:00 的时候,笔者在图书馆内就会发现外面在下雨,而且下雨的时间非常准时。总让人觉得新加坡是一个定时降雨的国家。正因为如此,在 NUS 总有各种各样的雨棚,可以让教职工和学生不需要淋雨从一栋楼走到另一栋楼,或者走向车站。从 NUS 数学系的 S17 到 S16 也是存在一条过街天桥的,当年每次思考数学遇到瓶颈的时候,就喜欢来这里透气,看一看外面的风景换一换思绪。

S17 的 4 楼办公室

在离开新加坡的前一个晚上(2015年7月17日晚上),笔者独自一人坐在 S17 的 4 楼会议室里,回想着这几年来新加坡生活的点点滴滴。从刚下飞机到进入 NUS 学习,从 Block 602 到 PGPR 再到 UTown,从通过博士资格考试到最终拿到博士学位。虽然经历了五年时间,但是每次回想起来却感觉是昨天的故事。正如歌词里唱的“有过多少往事,仿佛就在昨天;有过多少朋友,仿佛还在身边”。(未完待续)

2019年厦门游记

在公司这几年,每年都有外出进行团队建设的机会。所谓团队建设,就是一个部门或者跨部门的小伙伴们会组织到一起,由团长组织报名一个旅行团,大家可以在旅游期间交流工作心得与业务。笔者刚进公司的时候,错过了第一年的团队建设,但在后续的几年中每年都跟着团队一起出行,去过的地点包括台湾(2 次),老挝(1 次),厦门(1 次)。之前的游记均已按时写完,由于今年在疫情期间也不知道有没有出行的机会,于是写篇游记来回忆一下去年的厦门之行。

厦门一直是国内的旅游城市,其知名的景点非常多,包括南普陀寺,厦门大学,曾厝垵,中山路步行街,鼓浪屿等等。任何一个景点都足以让游客玩上大半天到一天的时间。整个团建的时间不算长,只有 3 天的时间,于是正好把这些景点都走一遍,也算是在忙碌的工作之余丰富一下大家的日常生活。

厦门景色

从深圳到厦门有很多出行方法,较为方便的还是从深圳北站坐高铁出发,3 小时 45 分钟左右就可以到厦门北站。高铁沿途游客可以欣赏周边的风景,也可以小憩一会补充睡眠,以便在下车之后有充足的体力进行游玩。为了能够有更多的时间进行游玩,旅行社安排大家乘坐早上的高铁,这样的话大家就可以在厦门吃午餐。因为深圳是一线大城市,每个人居住的地方也不太一样,于是旅行社就提供了两种方案供大家选择。一是住在公司附近的人可以选择赶到公司,早晨 6:30 乘坐大巴前往深圳北站;二是自行乘坐交通工具在 7: 40 之前到达深圳北站。不管怎么乘坐,都需要在规定的时间内赶到深圳北站,以免错过了行程。

深圳北站-厦门北站

本次厦门之行的人数有 28 人,也算是一个人数较多的旅行团。按照公司的标准,貌似成团人数少于 15 人就不能够出行,这次的厦门之行成团还算顺利,可能是由于扫尾团的缘故,就凑集了不少的同事一起出行。

在 2019 年 9 月 25 日这天,厦门之行正式开始。到达厦门之后第一个去的景点就是南普陀寺,它是国内的佛教寺院,烧香拜佛的人特别多。而南普陀寺的后山就是五老山,是厦门的著名风景区之一,来南普陀寺如果没有太多的事情的话,其实可以考虑从寺庙爬上五老山体验一下厦门的风景。

五老峰半山腰

南普陀寺的旁边就是厦门大学,但厦门大学是需要游客的身份证等证件才能够顺利进去的,并且其开放的时间比较短,目前应该是只有中午才能够开放的。但这也需要根据疫情的严重程度而定,去年还算会开放给游客,但是今年则不一定了,毕竟今年并不是一个太平年。

厦门大学

厦门大学旁边除了南普陀寺之外,还有一个著名的景点,那就是胡里山炮台。胡里山炮台始建于 1894 年光绪年间,里面分成站坪区,兵营区,后山区等部分。最著名的应该是有一门德国产的大炮,这应该是胡里山炮台最值得看的景点之一了。

胡里山炮台

从胡里山炮台出来,就可以走到海边,在海边除了沙滩之外,还有不少小贩在贩卖烧烤。如果有时间的话,在海边吃着烧烤,喝着啤酒也不失为一桩美事。

胡里山炮台背后的沙滩

之前去台湾旅游的时候,笔者每逢夜晚就会去台湾的夜市进行游玩,里面吃的玩的应有尽有。同样,厦门的夜市也是厦门的特色之一。而较为繁华的地点就是中山路步行街了,在这里不仅可以置办各种伴手礼带回去给同事,也可以购买一些礼物送给家人。如果实在是不知道买啥的话,就在步行街闲逛也是不错的选择。除了礼品店之外,各种各样的小吃店和果汁店也是逛街的必备。

中山路步行街

由于是跟着旅行团出行,于是住宿的条件其实还算不错,第一天(2019-09-25)住在岛内的一家酒店,而第二天(2019-09-26)则是全天都待在鼓浪屿,包括最后的住宿都在岛上。

第一晚的住宿

来了厦门旅游,不能错过的旅游景点自然就是鼓浪屿。鼓浪屿位于厦门的西南侧,这里汇聚了菽庄花园,日光岩,皓月园等著名的景点,在岛内沿途也有着很多不错的小吃。如果时间充裕的话,在岛内住一天体验一下生活也是不错的选择。

菽庄花园
日光岩

鼓浪屿岛上也有不少网红店,包括张三疯猫式奶茶,土耳其小哥的冰淇淋。有兴致的朋友一定不能够错过这些店。

冰淇淋小哥

鼓浪屿的夜晚与白天有着明显的区别,白天人声鼎沸,到处都是各种游客。但是到了夜晚则会安静下来,四处都只有海浪的声音,有很多店也会随着游客的离开而开始休息。

夜晚的鼓浪屿

到了第三天(2019-09-27),则是开始返程的日子,为了赶上下午的高铁,当天的行程就只安排了早上的曾厝垵。曾厝垵其实是一个小渔村,现在则成为了一个文化创意村,里面在卖各种各样的文艺物品和小吃。其实曾厝垵与台湾的九份山城并没有太多的区别,玩法和内容都差不了多少。

曾厝垵

可能是这次的行程已经花了足够的费用,于是这次的团建并没有安排购物的环节,饮食各方面也达到了之前所有团建的最佳水平。在刚进公司的时候也在十一期间去过厦门,这次重返厦门也算别有一番风味吧。

高铁返程

高考那些事

2020 年是一个不普通的年份,由于疫情的原因,各行各业都受到了巨大的影响,高考也因此从 6 月延期至 7 月。但在今年的高考前夕,却出现了一系列与高考有关的新闻,先是有艺人在直播中自爆在高考中获得不当利益,后又爆出了 XX 省份有一连串高考顶替的现象出现。

高考

自 1977 年 9 月高考恢复以来,在中国高考一直被誉为最公平的考试,考生们需要靠自身的考试成绩来决定自己未来的道路和发展方向。考试中每一分的差距都会给自己和家庭带来完全不同的人生道路。虽然随着社会的发展,城市的进步,各大城市的考生会有很多求学的机会,不管是通过竞赛保送,自主招生,出国留学,都可以帮助大城市的考生们进入心仪的大学。但是对于很多中小城镇的考生而言,高考则是少数几次可以改变自己人生的机会。不少考生会因为自身的成绩而与心仪的学校失之交臂,但是更加让人痛心的则是这段时间报道出来的一系列高考顶替事件。

所谓高考顶替事件,就是有人通过一些手段,将本来不属于自己的高考成绩和高校录取通知据为己有,顶替其他考生去读大学和走向职场。被顶替者通过高考获得的鲤鱼跃龙门机会则化为乌有,本来应该在大学读书的机会就永远再也不会出现。在当年各种通信尚不发达的年代,家庭条件不佳的被顶替者们可能根本就不知道这件事情,直到事后的十几年才逐渐爆出这些让人感到震惊的事情。

高考录取率

在 2011 年,南方周末的记者写了一篇文章《走到只剩下我一个》,该文撰写了一个从农村走出的大学生的一些人生经历,通过小学,中学,大学的求学之路,反映了一位农村大学生求学之路的艰辛和困苦。从文章中摘选其中的几段话如下:

等到小学毕业时,我所在的班级就只有三十三个人了,同村的同学就只有一个男孩子。初小那些同学,除了两三个留级,其余没有读书了。邻近几个村情况也都一样,辍学成为家常便饭,纵然是集镇上条件好的家庭也有很多人辍学,他们常是因为调皮被老师体罚,跑回家就再也不敢到学校了。

等到上高中时,整个年级就只有一个人是我小学的同学。对于很多家长来说,农村上学希望太过渺茫了,不如让孩子打工攒钱盖房子,盖好房子娶妻生子则是最实惠的选择。从小到大,我的那些同学们总会逐渐消失于上学的途中,出现在田间地头或者打工者拥挤的火车上。

今年我大学毕业,回想自己一路来的经历,如果说把我和同伴们所经历的教育过程比喻为一次探险,我更愿意相信自己只是一个走到最后的幸存者。

其实这样的事情并不罕见,在很多不发达的地区,对于孩子们而言,读书也许就是唯一改变命运的机会,否则就只能够去大城市打零工谋生。虽然也有一些学历普通的人能够通过创业的方式改变自身和家庭的命运,但是从整体来看,读书能够改变人生的概率其实还是比其他方式大许多的。

大学毕业前夕,我回家参加初小同学的婚礼,听到了一个好消息,一个坏消息。

好消息是,教过我们的大伯今年要退休了,这位有着43年教龄的乡村教师,回想职业生涯最得意的是,这辈子总算培养出一个大学生,也就是我。他的许多同事,穷尽一生也没教出一个。

坏消息是,村小班上的5个男生,如今就剩下我们俩了。其他三人辍学后到煤矿打工,被埋在了矿下面,回到村里的只有他们的骨灰盒。

每个考生的家庭条件是不一样的,家庭条件好的考生可以通过留学,自主招生,竞赛保送等很多很多的方式来进入高等院校。但是对于普通家庭条件的学生而言,通过读书参加高考则是少数几次可以改变自身命运的机会。一般情况下,人都会经历几个阶段:

  1. 婴幼儿阶段;
  2. 小学阶段;
  3. 中学阶段;
  4. 大学阶段;
  5. 职场阶段。
选择

在人生的早期,其实每个人没有太多的选择,毕竟那个时候会受到原生家庭的影响和限制。但是到了 18 岁左右,通过高考这一个公平的考试,每个人都拥有改变自己人生的机会。参加高考,每个人就可以离开原有的环境,继续提升人生的高度,就可以拥有更多的发展机会。如果高考这个考试不再公平,那么通过求学而改变人生的这条路也被堵死了,那么很多家庭条件欠佳的学生就再也没有上升的通道了。

记得当年在高考的时候,在进入考场的时候,每个学生都需要检查身份证,准考证,照片,是否携带电子设备。在中国,高考应该属于非常严格的考试之一。笔者身边很多同学也在高考之后进入了理想的院校进行求学之路,毕业之后也是在各自的工作岗位上发光发热。

今年在高考前夕则爆出了各种各样的事情,无论是艺人自爆在高考阶段通过不正当手段获利,还是 XX 省份的多起高考顶替事件,都会让人觉得高考是有一定的灰色地带的。在这些灰色地带,则是通过损害正常考生的合法权益而让靠各种手段投机取巧的考试获得了本不属于自己的利益。通过这些不正当的手段,考生们被迫改变了自己的命运,人生的发展之路无奈地被改变了。对于家庭条件欠佳的考生们而言,在人生发展的重要阶段出现了顶替事件,这样的损失恐怕已经不能够来用金钱衡量了。

人生之路

在人生的道路上,有些事一旦错过了就真的错过了。越走越远,根本不给你重来的机会。

新手宝爸爸和宝妈妈的待产包清单

作为新手宝爸爸和宝妈妈,在准备待产包的时候总是会觉得手足无措,一直在网上搜索各种资料,看各种资料的分析和讲解。在努力了一段时间之后,把整理好的资料写出来分享给大家。由于地域和医院不同的问题,可能会导致有一些细节不太一致,希望大家谅解。既然是新手,那么在整理的过程中难免会出现一些错误,希望大家及时指正。

蜡笔小新的婴儿时期

入院/就诊的时刻

按照医生的嘱咐,根据入院通知单的时间来入院。或者出现以下情况的时候来医院待诊等医生检查后确认是否入院。

  • 一胎规律宫缩:宫缩持续 30 秒以上,间隔 5-6 分钟;
  • 二胎不规律宫缩;
  • 胎膜破裂;
  • 胎动明显增多或者减少;
  • 异常阴道出血。

入院必知

入院的话,就需要根据医院的要求要准备相应的材料。除了在孕期日常需要按照流程来进行必要的产检之外,在孕期末尾最好提前准备好入院的材料,做到有备无患,不至于到了最后时刻手忙脚乱而不知所措。

孕期资料的准备

  • 深圳市的母子保健手册
  • 孕期所有检验报告单
  • 提前准备好以下三份报告单:B 超单(最新的一次),乙肝结果(9 – 13 周),GBS 结果(35 – 37 周)。

身份证件的准备

  • 身份证;
  • 社保卡;
  • 计划生育证明;
  • 结婚证;
  • 户口本;
  • 资金:因人而异,多退少补,可以使用现金,银行卡/信用卡,微信/支付宝
  • 银行卡/信用卡(出院退费约 7 个工作日返还);微信/支付宝(出院退费约 25 个工作日)。

新生儿落地费需自费,入院押金因人而异,多退少补。

陪护制度

不同的医院应该有着不太一样的陪护制度,这里的陪护制度仅供参考。就以即将入院的医院为例,会需要有以下几个要求:

  • 产妇入院之后不可私自外出,24 小时只能留一名陪护人员;
  • 探视时间可以有两名陪护人员,中午 11:30 – 12:30,晚上 18:00 – 20:00;
  • 查房时间:早上 8:30 – 10:00,陪护人员需要离开病房;
  • 禁止 12 岁以下的儿童进入病房;
  • 新型冠状病毒疫情期间:陪护人员需要戴口罩(自备口罩),产妇和陪护人员都需要做核酸检测(价格根据每个城市的情况来定),因此在办理入院手续的时候,就需要开核酸检测单,以便后续能够进行陪护;
  • 就餐方法:病区会提供冰箱,微波炉等常用电器,根据要求来使用即可。陪护人员可以自行通过外卖平台来订餐,月子餐需要看医院食堂是否有,如果有的话直接购买会方便不少。

宝妈妈的用品

通常来说,医院会告知妈妈们需要提前准备什么东西,就以即将入住的医院为例,医生们写了以下几样东西来提醒妈妈们:

  • 妈妈换洗衣服(2 – 3 套);
  • 洗漱用品;
  • 卫生用品:产褥垫(至少 20 张 60 * 90 CM),卫生巾,纸巾;
  • 防滑拖鞋(很重要);
  • 电动吸奶器(对于早产特别重要);
  • 眼罩,耳塞(建议准备,以便更好地休息)。
野原美伢准备待产包

以上是医院建议妈妈们需要带的最简化版本的待产包,如果想要舒适一点的话,其实可以根据各种资料持续准备更多的物品。一般来说,各种月子中心和网上的资料一般会提供更多的待产包资料。待产包可以分成以下几个部分:

  1. 卫生用品;
  2. 哺乳用品;
  3. 食物和餐具;
  4. 衣物类;
  5. 洗浴用品;

卫生用品包括:

  • 产褥垫:生产时用,至少 20 张 60 * 90 CM;
  • 卫生巾:可以选择产妇专用的卫生巾;
  • 成人纸尿裤:刚生产完的时候用,比较省事;
  • 刀纸;
  • 普通纸巾;
  • 一次性内裤:产后用比较方便;
  • 一次性马桶垫;
  • 口罩;
  • 剖腹产伤口贴(剖腹产);
  • 会阴冷敷垫(顺产);
  • 会阴坐垫(顺产有侧切);

哺乳用品包括:

  • 吸奶器;
  • 储奶袋;
  • 防溢乳垫;
  • 乳头防裂膏;
  • 乳头保护罩;

食物和餐具包括:

  • 巧克力和其他零食:顺产时补充体力;
  • 水或饮料:可以选择红牛/红枣桂圆汤,顺产时补充体力;
  • 吸管杯;
  • 弯头吸管;
  • 饭盒,筷子,勺子:需要买可以在微波炉使用的款式;
  • 洗洁精,洗碗布;
  • 水果刀,削皮器;

衣物类包括:

  • 换洗衣服(睡衣);
  • 哺乳胸衣;
  • 纯棉汗巾(长条);
  • 包脚拖鞋,防滑拖鞋;
  • 袜子;
  • 收腹带;
  • 月子帽;
  • 外套;
  • 产妇外出服;

洗浴用品包括:

  • 脸盆 & 洗脚盆等;
  • 会阴冲洗喷壶;
  • 免洗洗手液;
  • 梳子,镜子;
  • 防滑拖鞋:不要带一次性拖鞋,不防滑;
  • 毛巾,刷牙杯,牙刷,牙膏,漱口杯;
  • 洗面奶,护肤品(爽肤水,眼霜,乳液,防晒霜,唇膏);

杂物类包括:

  • 记事本,笔;
  • 手机,数据线,充电宝,充电器;

宝宝的用品

与妈妈的入院用品一样,医院同样会告知妈妈们需要提前准备宝宝的用品。医生们建议妈妈们准备好以下几样:

  • 宝宝换洗衣物,包被(2 -3 套);
  • 普通脸盆(沐浴用,约 40 * 40 CM);
  • 小毛巾 2 条,湿纸巾若干;
  • 纸尿裤若干;
  • 喂杯(自备,不建议用奶瓶)。
野原向日葵

同样的,宝宝的待产包也可以分成以下几个部分:

  1. 婴儿衣物;
  2. 卫生用品;
  3. 哺育用品;
  4. 洗浴用品;

婴儿衣物包括:

  • 和尚衣或者爬衣;
  • 肚围;
  • 肚脐贴/护脐贴:用来保护肚脐,洗澡必备;
  • 婴儿帽:出院的时候给宝宝带上帽子;
  • 袜子;
  • 包被:宝宝洗澡的时候或者出院时会用到;
  • 口水巾;
  • 纱布浴巾:宝宝洗澡时用,夏天也可以当做小杯子。
  • 纱布手帕:洗脸/洗澡用;

卫生用品包括:

  • 纸尿裤:准备 100 片左右,考虑透气性和吸水性;
  • 隔尿垫:可以准备反复使用/一次性使用的两种款式的;
  • 湿纸巾;
  • 棉柔巾;
  • 云柔巾;
  • 棉花棒;
  • 医用酒精:给宝宝消毒肚脐;

哺育用品包括:

  • 新生儿喂杯;
  • 软头勺;
  • 奶粉,奶瓶,奶嘴,奶瓶刷,奶瓶夹,奶瓶嘴清洁剂(禁止携带);
  • 蒸汽消毒锅:用来煮宝宝用的东西;
  • 暖奶器;
  • 恒温壶:冲泡奶粉用;
  • 小夜灯;

洗浴用品包括:

  • 脸盆,浴盆,小脸盆;
  • 水温计:小宝宝洗澡时量水温用;
  • 宝宝衣架;
  • 沐浴露,洗发液;
  • 婴儿专用指甲钳;
  • 液体爽身粉:预防尿布疹;
  • 润肤乳;
  • 护臀膏:改善尿布疹;
  • 抚触油;
  • 洗衣液:需要买婴儿专用的;

寝具和其他包括:

  • 婴儿床;
  • 耳温枪;
  • 婴儿背带;
  • 婴儿车;
  • 婴儿安抚玩具;
野原一家

除了待产包的准备之外,其实还有很多东西和资料需要查看,包括月子中心/月嫂,计划生育证明的办理,医院的定时产检等各种必须要提前准备的环节。后续将会持续完善待产包的清单和其他资料,供大家参考和讨论。

你真的适合当自由职业者吗?

你真的适合当自由职业者吗?

对于绝大多数人而言,大家基本上都是在公司,企业或者政府部门工作,借助平台和个人的力量来获得相应的报酬,那么一直从事这样的工作很可能会让人觉得日复一日,没有激情,创意不足。因此,就会有人向往一种自由自在的工作状态,看着别人发表旅游文章同时希望自己也能够过上说走就走的生活,看着别人开咖啡店的时候也想着自己啥时候也去开一个咖啡店。总之,最终要做到自己当自己的主人,不再为了一些工作上的琐碎事情所搅扰。

通常来说,自由职业者(self-employed)指的是自己雇佣自己,不属于任何组织,在自己的指导下找合适的项目做,通过自己的能力和付出来获取相应的报酬。如果要找到合适自己的项目,那么首先就要知道自己所擅长的领域是什么。有的人可能觉得自己特别擅长写作,可以靠自媒体写作来养活自己;有的人觉得自己擅长烹饪,因此可以通过开一家小店来盈利;有的人觉得自己讲课水平优秀,可以通过开一个培训班来实现财富自由。

说到这里,笔者就想到曾经在知乎上看到过一个问题,“普通人和专业运动员的差距有多大?”其中有一句话给我留下了深刻的印象,那就是“永远不要用你的业余爱好来挑战别人吃饭的本事”。意思就是你觉得你所擅长的东西其实在专业选手面前其实根本不值得一提。你觉得你自己擅长写作,但是你跟中文系,新闻转播专业的同学比起来怎么样?你觉得你擅长烹饪,但是你就能够保证做饭的水平能够超越专业厨师吗?你觉得你能够开培训班,但是你能够比专业的培训机构抢到更多的生源吗?结合自己的经历,之前也有不少的人说自己对数学有着浓厚的兴趣,特别想去攻读一个数学PHD学位,但是目前情况是只学过微积分,希望请教一下数学本科的相关书籍和学习步骤。这种时候只要向他推荐一本 Rudin 的《数学分析原理》,基本上也就没有然后了。因此,一个人觉得自己非常擅长的某个领域很可能只是一种错觉,因为在职业选手面前实在是不堪一击。

在公司的时候,基本上还不太需要担心自己没有事情可以做,按部就班地工作就能够获得相应的报酬。但是一旦成为了自由职业者,有很多的事情就必须要自己一个人去面对,例如如何选择合适的项目,如何与客户沟通,如何保证项目的合理进展,如何保证合同的顺利签署等等,所有繁杂的事情都压在了一个人的身上。在这种时候,自由职业者就必须要向市场证明自己的价值,否则很可能连一份合同都拿不到,甚至连自己的赚钱系统都无法顺利的搭建。最后很可能证明的事情就是,你之前觉得你所擅长的事情,其实在市场上根本一文不值。

就算有了自己的赚钱渠道,例如自媒体写作,开咖啡店等。怎么安排自己的工作时间就是另外一个问题了。读过PHD的人都知道,除了那些整天要去实验室做实验的PHD们,理论研究的PHD们时间一般来说是相对自由的。在自由的时间里,有多少PHD是做了有价值的事情呢?我想大部分可能还是陷入拖延症的漩涡里不能够自拔吧。每天早起就是看电视,中午玩游戏,下午稍微看看论文,然后晚上就外出吃饭聚餐。除此之外,如果家人或者朋友觉得你是自由职业者,都会觉得你十分的悠闲,时不时的可能让你去拿个快递,寄封信件,然后陪他们出去聚餐等。这样的话,其实每天的工作时间就会十分的有限,工作效率也会大打折扣。因此,即使有了工作渠道,能否制定合适的工作计划和时间安排,也是自由职业者必须面对的问题。

在读书或者工作的时候,都会有人觉得迷茫,觉得这份工作或者继续读书没有价值。在从事自由职业的时候,这种迷茫与彷徨的感觉可能会更加强烈。例如,上个月没怎么努力就赚到了5000块钱,但是这个月努力了很久,却只收到了3000块。不稳定性和不确定性很容易让一个人的内心产生迷茫与彷徨,而且这种时候身边的人也不会理解你,因为他们很可能不是自由职业者。要解决这种问题其实只能够靠自己或者进入一个自由职业者的圈子里面,看一看别人是怎么解决这类问题的。但是,即使别人告诉你他的经验,也不见得对你有多大的帮助。对于时间相对自由的工作岗位,例如拿到 tenure 的大学教授,工作不是很繁忙的职员。在保证工作稳定的情况下,可以在工作之余尝试一下自己的兴趣爱好能否挣到钱,是否在市场上具有一定的竞争力。这样做的话能够尽可能的降低自己的风险。

综上所述,要判断一个人是否适合自由职业,首先要看以下几点:

  1. 自己拥有的技能是否真的有市场,能否给自己真正带来收入;
  2. 对自己的要求是否高,在日常的生活中自律性是否足够强;
  3. 对自己的未来是否有较为清晰的规划,是否能够扛住短期没有收入的风险。

如果不清楚以上几点,那么就不适合当自由职业者;如果能够清楚的知道以上几点,可能就具备了自由职业者的基本素质。

张戎 数学人生 2017-04-04

大数据领域的近似分析方法(一)

基数估算问题

基数估算(Cardinality Estimation),也称为 count-distinct problem,一直是大数据领域的重要问题之一。顾名思义,基数估算就是为了估算在一批数据中,它的不重复元素有多少个。

这个问题的应用场景十分广泛。例如:对于 Google 主页面而言,同一个账户可能会访问 Google 主页面多次。于是,在诸多的访问流水中,如何计算出 Google 主页面每天被多少个不同的账户访问过就是一个重要的问题。那么对于 Google 这种访问量巨大的网页而言,其实统计出有十亿 的访问量或者十亿零十万的访问量其实是没有太多的区别的,因此,在这种业务场景下,为了节省成本,其实可以只计算出一个大概的值,而没有必要计算出精准的值。

从数学上来说,基数估计这个问题的详细描述是:对于一个数据流 x_{1},x_{2}, \cdots, x_{s} 而言,它可能存在重复的元素,用 n 来表示这个数据流的不同元素的个数,i.e. n=|\{x_{1},\cdots,x_{s}\}|, 并且这个集合可以表示为 \{e_{1},\cdots,e_{n}\}. 目标是:使用 m 这个量级的存储单位,可以得到 n 的估计值 \hat{n}, 其中 m\ll n, 并且估计值 \hat{n} 和实际值 n 的误差是可以控制的。

如果是想得到精确的基数,可以使用字典(dictionary)这一个数据结构。对于新来的元素,可以查看它是否属于这个字典;如果属于这个字典,则整体计数保持不变;如果不属于这个字典,则先把这个元素添加进字典,然后把整体计数增加一。当遍历了这个数据流之后,得到的整体计数就是这个数据流的基数了。

cardinality_estimation_naive_solution
Naive Solution

这种算法虽然精准度很高,但是使用的空间复杂度却很高。那么是否存在一些近似的方法,可以估算出数据流的基数呢?其实,在近几十年,不少的学者都提出了很多基数估算的方法,包括 LogLog,HyperLogLog,MinCount 等等。下面将会简要的介绍一下这些方法。

cardinality_estimation_survey_table_1
基数估计的部分算法

HyperLogLog 的理论介绍

HyperLogLog 是大数据基数统计中的常见方法,无论是 Redis,Spark 还是 Flink 都提供了这个功能,其目的就是在一定的误差范围内,用最小的空间复杂度来估算一个数据流的基数。

Spark
Spark 的 Logo

HyperLogLog 算法简要思路是通过一个 hash 函数把数据流 \mathcal{D} 映射到 \{0,1\}^{\infty}, 也就是说用二进制来表示数据流中的元素。每一个数据流中的元素 x 都对应着一个 0,1 序列。

在介绍 HyperLogLog 之前,我们可以考虑这个实际的场景。在一个抛硬币的场景下,假设硬币的正面对应着 1, 硬币的反面对应着 0; 依次扔出 0,0,0,1 的概率是多少?通过概率计算可以得到是这个概率是 1/2^{4}=1/16. 那么相当于平均需要扔 16 次,才会获得 0001 这个序列。反之,如果出现了 0001 这个序列,说明起码抛了 16 次硬币。

考虑这样一个 0,1 序列,w=w_{1}w_{2}\cdots, w_{i}\in\{0,1\}, i\geq 1,k 表示第一个 1 出现的位置。也就是说 w_{1}=w_{2}=\cdots=w_{k-1}=0. 那么在扔硬币的场景下,出现这样的序列平均至少需要扔 2^{k} 次。对于一批大量的随机的 0,1 序列, 可以根据第一个 1 出现的位置来估算这批 0,1 序列的个数。也就是说:

  • 出现序列 1XXXXX 意味着不重复的元素估计有 2^1=2 个;
  • 出现序列 01XXXX 意味着不重复的元素估计有 2^2=4 个;
  • 出现序列 001XXX 意味着不重复的元素估计有 2^3=8 个;
  • 出现序列 0001XX 意味着不重复的元素估计有 2^4=16 个。

于是,对于随机的 0,1 序列,可以定义函数 \rho(w_{1}w_{2}\cdots) 来表示 1 出现的第一个位置。i.e. \rho(1XXXXX)=1, \rho(01XXXX)=2, \rho(001XXX)=3, \rho(0001XX)=4.

简单来看,其实 HyperLogLog 的基数统计就使用了这样的思想,通过二进制中 1 出现的第一个位置来估算整体的数量。首先把这批元素通过 hash 函数处理成 0,1 序列,然后把这批 0,1 序列都放入 1 个桶,然后通过计算这个桶里面所有 0,1 序列的 \rho(w) 的最大值,就可以预估出整体的数量。i.e. M=\max_{w}\rho(w), 整体的数量预估是 2^{M}=2^{\max_{w}\rho(w)}.

  • 1 个桶:计算出 M=\max_{w}\rho(w), 预估不重复的元素个数是 2^{M}.

那么如果只有 1 个桶,其实是会存在一定的偏差的。为了解决这个问题,一种想法就是重复以上操作,从 hash 函数开始处理成 0,1 序列,每次都把这批 0,1 序列放入 1 个桶,每次获得一个 M 值。总共操作 m 次,第 j 次操作得到的值记为 M_{j}; 于是就可以对 \{M_{1},\cdots,M_{m}\} 进行均值处理,可以使用以下方法:

  • 算术平均数:M=\sum_{j=1}^{m}M_{j};
  • 几何平均数:M=\sqrt[m]{M_{1}\cdots M_{m}};
  • 调和平均数:M=m/\sum_{j=1}^{m}M_{j}^{-1};
  • 中位数:M = median\{M_{1},\cdots,M_{m}\}.

从而可以预估整体的数量为 2^{M}.

如果按照以上的步骤进行操作,就是需要重复进行多次操作,在足够多的情况下,其实是没有必要那么操作的。HyperLogLog 也是用了多个桶,但是用了一个截断的技巧。对于一个 0,1 序列 x=\cdots x_{b+2}x_{b+1}x_{b}\cdots x_{1}, HyperLogLog 从某个位置 b 开始,低位 x_{b}\cdots x_{1} 用于决定桶的序号,也就是第几个桶。桶的个数就是 m=2^{b}, 高位 \cdots x_{b+2}x_{b+1} 用于估算放在桶里面的元素个数。

每次都可以获得一个值,也就是桶里面第一次出现

  • 第 1 个桶:计算出 M_{1}=\max_{w}\rho(w), 预估元素个数 2^{M_{1}};
  • 第 2 个桶:计算出 M_{2}=\max_{w}\rho(w), 预估元素个数 2^{M_{2}};
  • ….
  • m 个桶:计算出 M_{m}=\max_{w}\rho(w), 预估元素个数 2^{M_{m}};

均值的计算,HyperLogLog 使用了调和平均数 m/\sum_{j=1}^{m}2^{-M_{j}} 来估算桶里面的元素个数,那么在有 m 个桶的情况下,整体的元素个数就可以估算为 E=m^{2}\cdot\bigg(\sum_{j=1}^{m}2^{-M_{j}}\bigg)^{-1}.

hyperloglog_algorithm_simple
原始的 HyperLogLog 算法

其中的 \alpha_{m}=\bigg(\int_{0}^{+\infty}\bigg(\log_{2}\bigg(\frac{2+u}{1+u}\bigg)\bigg)^{m}du\bigg)^{-1}.m=1 的时候,\int_{0}^{+\infty}\log_{2}\bigg(\frac{2+u}{1+u}\bigg)du 是发散的;当 m\geq 2 的时候,\int_{0}^{+\infty}\bigg(\log_{2}\bigg(\frac{2+u}{1+u}\bigg)\bigg)^{m}du 是收敛的。因此,在使用这个算法的时候最好放入 m\geq 2 个桶。

HyperLogLog 分成两块,第一块就是 add 模块,用于分桶和统计;

for v in M:
    set x := h(v);
    set j = 1 + <x(b),...,x(2),x(1)>;
    set w := x(b+1)x(b+2)...; 
    set M[j] := max(M[j], \rho(w));

在 HyperLogLog 算法中,对于集合 \mathcal{M} 中的每一个元素 v\in\mathcal{M}, 可以通过 hash 函数转换成一个 0,1 序列 h(v)=x=<\cdots x_{b+2}x_{b+1}x_{b}\cdots x_{1}>, 其中 x_{1} 表示二进制中的最低位,x_{2} 表示次低位。

然后可以通过 <x_{b}\cdots x_{1}>_{2} 来计算放在第 j 个桶,这里 j=1+<x_{b}\cdots x_{1}>_{2}. 同时将 x 的高位拿出来,也就是 x_{b+1}x_{b+2}\cdots, 计算这批序列的 \rho 函数的最大值,然后记为 M_{j}; 这一步也可以称为 merge 模块,也就是进行更新合并。

compute Z := (\sum_{j=1}^{m}2^{-M[j]})^{-1};

上一步就是 HyperLogLog 的另外一步,count 模块,于是,进一步估算出 E=\alpha_{m}m^{2}Z.

HyperLogLog 的空间复杂度特别低,大约是 O(m\log_{2}\log_{2}n) 这个量级的,其中 m 是桶的个数,n 是基数。HyperLogLog 的时间复杂度则是 O(n), 只需要遍历一遍所有元素即可得到最终结果。

  • 假设基数为 2^{k}, 二进制就是 k 位,1 最晚就会出现在第 k 个位置上;而 k 只需要 log_{2}k 个 bit 就能够存储;
  • 假设基数为 2^{64}, 二进制就是 64 位,1 最晚会出现在第 64 个位置上;而 64 需要 6 个 bit 就可以存储。

hyperloglog_algorithm_compare
算法对比

在论文中,论文 “Hyperloglog: the analysis of a near-optimal cardinality estimation algorithm” 的作者们针对各种算法进行了对比,其实 HyperLogLog 的空间复杂度是非常小的,并且误差也在可控的范围内。

hyperloglog_algorithm_theorem
HyperLogLog 的定理证明

在论文 “Hyperloglog: the analysis of a near-optimal cardinality estimation algorithm” 作者们得到上述定理,精准的给出了 HyperLogLog 算法的误差估计。因此,HyperLogLog 算法其实是有数学定理证明的。

以上只是获得了理论上的 HyperLogLog 算法,但是在实战中,其实是需要进行微调的。主要的微调部分是根据理论中的 E 值来进行调整。将 E 值进行调整的话,情况可以分成三种:

  • 小范围;
  • 中等范围;
  • 大范围;

hyperloglog_algorithm_practical
实战中的 HyperLogLog

Case(1):小范围

在小范围的情况下,E\leq 5m/2, 此时的基数相对于桶的数量而言不算太多,因此可能存在多个空桶,需要进行调整。

可以思考这样一个问题:假设有 m 个桶,同时有 n 个球,把这 n 个球随机往这 m 个桶里面扔,每个球只能够进入一个桶,那么空桶个数的期望是多少个?

Answer:假设 A_{1},\cdots,A_{m}m 个桶,

P(A_{j}=\emptyset)=\bigg(1-\frac{1}{m}\bigg)^{n} 表示桶 A_{j} 空的概率;

P(A_{j}=\emptyset \cap A_{k}=\emptyset)=\bigg(1-\frac{2}{m}\bigg)^{n} 表示桶 A_{j}, A_{k} 同时为空的概率(j\neq k);

那么空桶个数的期望就是 m\cdot\bigg(1-\frac{1}{m}\bigg)^{n},m,n 充分大的时候,约为 me^{-n/m} 个。

因此,在小范围的情况下,如果空桶的个数 V\neq 0, 那么可以更新为 m\ln(m/V). 事实上,可以通过 V=me^{-n/m} 解出 n=m\ln(m/V).

Case(2):中等范围

E 值不作调整。

Case(3):大范围

E>2^{32}/30, 那么更新为 E^{*}=-2^{32}\ln(1-E/2^{32}), 其中 E^{*}>E.

通过这样的方法,E^{*} 的误差大约在 \pm 1.04/\sqrt{m} 左右。

除此之外,\alpha_{m} 其实也可以用近似值来代替,毕竟如下公式的计算是有一定的成本的。

\alpha_{m}=\bigg(\int_{0}^{+\infty}\bigg(\log_{2}\bigg(\frac{2+u}{1+u}\bigg)\bigg)^{m}du\bigg)^{-1}.

近似的值为 \alpha_{16}=0.673, \alpha_{32}=0.697, \alpha_{64}=0.709, \alpha_{m}=0.7213/(1+1.079/m)m\geq 128.

HyperLogLog 的案例分析

有一个关于 HyperLogLog 的 demo 网站可以看到 HyperLogLog 的算法过程,其链接是 http://content.research.neustar.biz/blog/hll.html

在这个 demo 中,作者对比了 LogLog 和 HyperLogLog 的区别和运行过程,有助于大家理解整个过程。其中 LogLog 与 HyperLogLog 的区别就在与它们平均值的处理方式不一样,前者是使用算术平均值,后者是使用调和平均值。

  • LogLog\alpha_{m}\cdot m\cdot 2^{\sum_{j=1}^{m}M_{j}/m};
  • HyperLogLog\alpha_{m}\cdot m^{2}\cdot\bigg(\sum_{j=1}^{m}2^{-M[j]}\bigg)^{-1};

hyperloglog_demo_1
HyperLogLog Demo:初始化

hyperloglog_demo_2
第一个 hash 值:3852172429

3852172429 的二进制是:11100101100110110111110010001101,可以划分为100 110110111110010 001101。最后的六位是 001101,十进制就是 13,那么这个数字就会被放入第 13 个桶;而 110110111110010(从低位到高位看),\rho 函数的值就是 2;于是在第 13 个桶就会把 0 更新成 2。

hyperloglog_demo_3
第二个 hash 值:2545698499

2545698499 的二进制是 10010111101111000100011011000011,用同样的分析可得结论。

hyperloglog_demo_4
第三个 hash 值:2577699815

2577699815 的二进制是 10011001101001001001001111100111。

hyperloglog_demo_5
第四个 hash 值:775376803

775376803 的二进制是 101110001101110100111110100011。

hyperloglog_demo_6
运行结束

从以上的 Demo 运行过程可以看出,整个 HyperLogLog 的算法逻辑还是相对清晰的,其整个算法的亮点应该在于借助了抛硬币的场景,用抛硬币的结果来估算抛硬币的次数。

参考文献:

  1. Count-distinct Problem 的维基百科:https://en.wikipedia.org/wiki/Count-distinct_problem
  2. Heule, Stefan, Marc Nunkesser, and Alexander Hall. “HyperLogLog in practice: algorithmic engineering of a state of the art cardinality estimation algorithm.” Proceedings of the 16th International Conference on Extending Database Technology. 2013.
  3. Flajolet, Philippe, et al. “Hyperloglog: the analysis of a near-optimal cardinality estimation algorithm.” 2007.
  4. HyperLogLog 的 demo 网站:http://content.research.neustar.biz/blog/hll.html

统计与大数据专业究竟在学什么?

统计学是一门关于数据分析的学科,用于测量,收集,整理,归纳和分析数据的真实情况和估算情况。统计学从 17 世纪的中期逐渐发展起来,不仅存在于概率与数理统计领域,还广泛应用在各种自然学科,社会科学和人文科学上,也会被用于各种团队,企业和国家的决策。随着大数据时代的到来,统计学也与计算机,信息学等领域紧密结合,是数学科学的有力工具之一。

概率论_2
正态分布

描述统计学(descriptive statistics)又称为叙述统计,是统计学中用于描述和总结所观察到对象的基本统计信息的一门学科。描述统计的结果是对当前已知的数据进行更精确的描述和刻画,分析已知数据的集中性和离散性。描述统计学通过一些数理统计方法来反映数据的特点,并通过图表形式对所收集的数据进行必要的可视化,进一步综合概括和分析得出数据的客观规律。与之相对应的是推断统计学(statistical inference),又称为推断统计,是统计学中研究如何用样本数据来推断总体特征的一门学科。推断统计学是在对样本数据描述的基础上,对总体的未知数据做出以概率形式来描述的推断。推断统计的结果通常是为了得到下一步的行动策略。以上的两个统计学方向都属于应用统计学。

population_and_sample
总体和样本

在有的学校,统计专业是放在数学系里面的,而有的学校则是把统计和数学分开,形成数学系(Department of Mathematics)和统计系(Department of Statistics)。无论分开还是合并,一般情况下都是放在理学院(Faculty of Science)的。

NUS_Stat_Logo
NUS 统计与应用概率系

统计系和数学系的低年级课程是十分接近的,基本上还是数学分析,线性代数,概率论等一系列的课程。

Module_Level_1_2
Level 1000 和 Level 2000

到了高年级之后,所学的课程与数学系的课程就会出现明显的区别。数学系的学生会学习实分析,复分析,泛函分析等一系列课程。而统计系的学生会学习回归分析,随机过程,数据分析,贝叶斯分析等诸多课程。统计系的学生更偏向应用一些,数学系的学生课程则会更加理论一些。

Module_Level_3_4
Level 3000 和 Level 4000

从 NUS 在 2020 的 E-Open House 的资料可以看出,统计专业的学生,其就业方向也是十分宽泛的,可以考虑去银行,金融机构就职;也可以考虑去咨询公司,也可以去政府或者教育机构找到合适自己的工作。

统计的行业需求
统计专业的行业需求

对于第四年的学生,如果在国内的话,一般情况下会选择保研,考研,找工作,甚至出国留学。有的学生也会选择去找一个长达半年到一年的实习。这个就根据每个同学的实际情况而定了,但是绝大部分也就是这几个选择,或者有人也会选择 gap 一年修正一下。

简要课程安排_3
最后一年的项目

相对于数学系,统计系的课程安排更加偏向于实战与应用,并且其实用性也会高于数学系的理论课程。如果未来要从事数据分析,商业分析等方向的话,其实攻读统计系是一个还不错的选择。

在新加坡国立大学的统计与应用概率系,除了统计系这一经典的专业之外,还提供了数据科学与分析(Data Science and Analytics)这一个新兴专业供学生选择。

众所周知,随着科技时代的到来,数据的增加是非常迅速的,无论是用户自身产生的数据,还是平台方产生的数据,都是十分巨大的。数据的增大那就意味着需要使用各种各样的计算机,统计,数学方面的技术来解决现有的疑难杂症,于是大数据时代的技术也逐渐映入大家的眼帘。

DataScience_1
数据趋势

无论是国内还是国外,都在提倡智慧城市这一概念,那么在智慧城市中,大数据技术就是一个绕不开的话题。各行各业都将会使用大数据系统来做各种服务,包括推荐系统(Recommender Systems),高频交易,风险管理,移动支付等等。通过这些技术,人们的生活质量将会大大提升。通过这些产品,科技将会给人们带来诸多便利。

DataScience_3
智慧城市

而数据科学是一门交叉学科,它需要使用到计算机科学(Computer Science)数学(Mathematics)统计学(Statistics)等多种学科的技术和知识点。如果要应用在金融领域,还会要求从业者掌握金融方面的知识。因此,数据科学在这个时代背景下是具有实用性的,也是很多行业的发展趋势。

DataScience_4
数据科学

从其课程设置也可以看出,学生们所学的课程包括编程,数据结构与算法,也包括微积分和线性代数,还有统计学等诸多基础课。在高年级的时候,将会学习人工智能,计算与优化,数据库,数据处理,机器学习等课程。除此之外,在具体做项目或者实习的时候,将会根据方向的需要来学习相关的业务知识,涵盖了金融,医药,调度优化等诸多领域。

DataScience_6_Essential_Modules

DataScience_7_Elective_Modules
课程设置

整体来看,统计与数据科学专业是以实用性为目的,培养学生的理科思维,动手能力和数据分析能力的一门学科。如果学生希望学习理科并且将来学以致用的话,其实选择统计或者数据科学是一个不错的选择。

参考资料:

  1. NUS E-Open House:2020,YouTube 视频;
  2. http://www.stat.nus.edu.sg:NUS 统计系官网。

《软技能:代码之外的生存指南》

《软技能:代码之外的生存指南》是笔者刚刚进入公司工作,开始职场生涯的时候,一个偶然的机会从同事那里看到的一本书。从其内容提要可以看出,这是一本关注软件开发人员自身发展的书籍,书中讲了 7 个部分,包括:

  1. 职业;
  2. 自我营销;
  3. 学习;
  4. 生产力;
  5. 理财;
  6. 健身;
  7. 精神。

软技能_Cover
《软技能:代码之外的生存指南》

本书的作者从自身的亲身经历出发,按照以上 7 个方面给大家介绍了软件开发人员的自我发展历程,包括程序员的职场发展,程序员的自我营销策略,程序员如何培养学习习惯,程序员如何提升自己的生产力,如何培养良好的理财习惯健身将会带来多少好处,精神将会如何提升自我的能力。通过阅读这本书,程序员确实可以从作者的字里行间学习到很多东西,并且积极思考自己的职业生涯,丰富自己的业余生活,让自己的生活更加丰富多彩。

从作者的自我介绍可以得知:John Z. Sonmez 是 “Simple Programmer” 网站的创始人,他为在线培训机构 Pluralsight 开发了 50 多门在线课程,其领域涉及 iOS,Android,.NET,Java 和游戏开发等诸多主题。他还是 “Get Up and CODE” 的主持人,并且在这里讨论关于程序员健身的话题;他也是 “Entreprogrammers” 的播客主持人,他在此与其他人分享构建在线业务的真实故事。

John Z. Sonmez 是不少程序员的人生导师,通过他写的教材,讲授的课程,传递的人生故事,让不少的程序员了解到了前辈的发展历程,并且能够启发程序员如何才能够过上更加充实的生活。通过“化繁为简”的方法,传授给程序员让他们达成自身目标的力量与动力。

下面来摘选一下本书中的经典语录:

Chapter 1:职业

就业选择:列出你的选择:

  1. 雇员:对广大软件开发者而言,这是一项常见的,默认的就业选择。身为雇员的最大好处就是稳定。
  2. 独立咨询师:独立咨询师通常有自己的公司,依照合同为客户工作,但并不与任何一个客户绑定。做独立咨询师最大的好处可能就是赚钱的潜力。
  3. 创业者:创业之路可能是你职业生涯中最难,最不确定但却最具回报潜力的选择。雇员和独立咨询师都在以时间换金钱,而创业者尽管换不来预付的报酬,但是他却有机会在未来获得更大的收益。创业者的两大优势:完全自由和完全不封顶的赚钱潜力。

软技能_Table_6_1
优点与缺点

选择什么完全取决于你自己,并且你也可以随时切换路径。

成为专业人士:

  1. 一切都始于习惯。习惯是成为专业人士必不可少的部分。需要培养自己的专业习惯,需要具备时间管理技能。
  2. 坚守正道。专业人士必须对工作的优先级做出艰难的抉择。
  3. 追求品质,完善自我。你必须不断改善和提高自己的工作品质。

Chapter 2:自我营销

自我营销的正确方式就是为他人提供价值。成功进行自我营销的关键在于:如果想让别人喜欢你,想和你一起工作,你就必须要为他们提供价值。

你也许是世界上最有天赋的软件开发人员,但是如果没有人知道你的存在,你也只不过是浮云一片。

软技能_Table_19_1
自我营销的方式

打造引人注目的品牌

  1. 品牌所需要传递的信息;
  2. 品牌的一致性;
  3. 品牌的视觉符号;
  4. 品牌的曝光率。

创建大获成功的博客

  1. 打造成功博客的最大秘诀有且仅有一个—持之以恒;
  2. 只是持之以恒还不足以使你的博客大获成功,你还应该确保你写的都是高质量的内容。
  3. 重视博客内容品质的另一个重要原因是为你的博客提供更有价值的链接。
  4. 在起步之初,你的博客很可能会很糟糕。但是,随着不断尝试贡献出优秀的内容,而不是将自己脑子里的东西随意丢在网上,不考虑格式和结构还有一大堆拼写错误,你终会成功。

软技能_Table_23_1
通过社交媒体分享的内容

Chapter 3:学习

十步学习法

  1. 第 1 步:了解全局;
  2. 第 2 步:确定范围;
  3. 第 3 步:定义目标;
  4. 第 4 步:寻找资源;
  5. 第 5 步:创建学习计划;
  6. 第 6 步:筛选资源;
  7. 第 7 步:开始学习,浅尝辄止;
  8. 第 8 步:动手操作,边玩边学;
  9. 第 9 步:全面掌握,学以致用;
  10. 第 10 步:乐为人师,融会贯通

知识短板会阻碍你的进步。准确识别它们的最佳方式之一就是看看自己在哪些工作上花费了大量的时间。或者一直在进行重复性劳动。

任何你所做的重复性工作都值得彻查一番。

另一种识别知识短板的方法就是,时刻都要试图了解自己不理解或不清楚的事物。

软技能_Table_35_1
检查知识短板

Chapter 4:生产力

生产力提升计划:我的生产力提升计划的基本思路就是,我把一周的时间分配给一个一个用时不超过两小时的小任务。

  1. 季度计划:在做季度计划时,我会尽力列出我想在本季度完成的每一个大项目,我还会制定一些较小的目标。
  2. 月计划;每个月的第一天我会打印出当月的月历,并且规划出每天要完成的工作。
  3. 周计划;每周一的早晨,我会做我的周计划。
  4. 日计划及执行:要计划好这一天,我首先要把对应日期里的卡片移到“今天”这一栏,并把它们按照重要性排序。我要保证自己优先完成最重要的事情。

一些常见的时间杀手

  1. 看电视;
  2. 社交媒体;
  3. 新闻网站;
  4. 不必要的会议;
  5. 烹饪:因人而异;
  6. 玩电子游戏(尤其是网络游戏);
  7. 工间喝咖啡休息:因人而异。

软技能_Table_48_1
任何行动都比不采取行动好

Chapter 5:理财

软技能_Table_49_1
资产与负债

Chapter 6:健身

可能的健身目标:

  1. 减肥(减掉脂肪);
  2. 增肌(增长肌肉);
  3. 增加力量(不一定是增长肌肉);
  4. 增加肌肉耐力(改善运动表现);
  5. 改善心血管健康;
  6. 在某些运动上表现更好。

Chapter 7:精神

积极思考问题的根源是这样一种信念—你比你所处的环境更伟大。这种信念让你总能先看到事物好的一面,因为无论身处任何环境,你都有能力改变自己的未来。这是人类成就的最高信念,是世界上最强大的力量。

从更现实的层面来讲,积极思考就是选择从好的一面(而不是从坏的一面)去思考问题。

畏惧失败似乎是大多数人的本能。

失败不同于被打败。失败是暂时的,被打败是永恒的。

不要畏惧失败,要拥抱失败。不只是因为失败和被打败不同,还因为失败是通往成功的必经之路。

结束语

感谢你抽出时间来阅读这本书,并真诚地希望你能在本书中发现一些永久的价值。

 

时间序列异常检测—节假日效应的应对之道

在时间序列异常检测中,通常有一个较为常见的场景就是“节假日效应”。所谓节假日效应,指的就是在节假日的时候,其时间序列的走势跟日常有着明显的差异性,但是又属于正常的情况。从国内 2020 年的节假日安排可以看出,一年中有好几个关键的假日:

  1. 元旦:1 天;
  2. 春节:7 天;
  3. 清明节:3 天;
  4. 五一劳动节:5 天;
  5. 端午节:3 天;
  6. 国庆节:8 天。

在这些节假日的时候,为了调休,自然也会带来工作日上的调整。例如:在 2020 年 1 月 19 日,2020 年 2 月 1 日是需要上班的(虽然今年受疫情影响最终也没上班)。因此,在这些节假日进行调整和变化的时候,各种各样的业务指标(时间序列)通常也会发生变化,变得跟以往的走势不太一致。因此,如何解决节假日效应的时间序列异常检测就是业务上所面临的问题之一。

£¨Í¼±í£©[Éç»á]2020Äê½Ú¼ÙÈշżٰ²ÅŹ«²¼
2020 年的放假安排
清华大学的 Netman 实验室在 2019 年发表了一篇论文,专门用于解决时间序列异常检测中的节假日效应问题,论文的标题是《Automatic and Generic Periodic Adaptation for KPI Anomaly Detection》。在本文中,所用的时间序列是关于各种各样的业务指标的,包括搜索引擎,网上的应用商店,社交网络数据等等。作者们针对 KPI(Key Performance Indicator)做了时间序列异常检测,并且发明了一种方法来避免节假日效应的问题。论文针对时间序列的工作日(work days),休息日(off days),节假日(festival)做了必要的区分,然后将时间序列的不同时间段进行合理地拆分和组装,再进行时间序列异常检测,从而在一定的程度上解决节假日效应问题。

节假日效应_Fig1
实际案例(1)

在实际的案例中,我们可以看到,同一条时间序列的走势在工作日(work day),休息日(off day),春节(Spring Festival)明显是不一样的。因此,根据工作日的时间序列走势来预测春节的走势明显是不太合理的;同理,根据春节的走势来预测休息日的走势也会带来一定的偏差的。那么如何解决节假日效应的问题就成为了本篇论文的关键之一。

节假日效应_Fig3
实际案例(2)

在上图中,我们可以看到论文中使用的数据都具有某种周期性(Periodicity)。KPI A,B,C 都是具有明显具有工作日和周末特点的,在工作日和周末分别有着不同的形状;KPI D 则是关于网上应用商店周五促销的,因此在周五周六的时候,其实时间序列会出现一个尖峰(peak);KPI E 的话则是每隔 7 天,会有两个尖刺,然后并且迅速恢复;KPI F 的话则是可以看出时间序列在十一的走势跟其余的时间点明显有区别。除此之外,对于一些做旅游,电商等行业的公司,其节假日效应会更加突出一点,而且不同的业务在节假日的表现其实也是不一样的。有的时间序列在节假日当天可能会上涨(电商销售额),有的时间序列在节假日当天反而会下降(订车票,飞机票的订单量)。因此,在对这些时间序列做异常检测的同时,如何避免其节假日效应就是一个关键的问题了。

而在实际处理的时候,通常也会遇到几个常见的问题;

  1. 周期性的多样性:通过实际案例可以看出,对于不同的时间序列,其周期是完全不一样的,而且在不同的周期上也有着完全不同的表现;
  2. KPI 数量巨大:这个通常来说都是智能运维领域中的常见问题;
  3. 周期的漂移:一般来说,通过时间序列的走势我们只能够看出一个大致的变化,但是具体到细节的话,周期是存在一定的波动的。例如不一定恰好是 7 天,有可能是 7 天加减 5 分钟之类的周期。这个跟业务的具体场景有关系,也跟当时的实际情况有关。

于是,基于这些挑战,作者们希望提出一个健壮的机器学习算法来解决这个问题,本文的系统被作者们称之为 Period,正好也象征着解决节假日效应这个寓意。

Period_Fig7
Period 的整体架构

从论文中可以看出 Period 的整体架构如上图所示,包括两个部分:

  1. 离线周期性检测(offline periodicity detection);
  2. 在线适应性异常检测(online anomaly detection adaptation)。

在第一部分,每一条时间序列都会被按天切分成很多子序列(subsequence),然后将其聚集起来,把相似的时间序列放在一类,不相似的放在另外一类;在第二部分,新来的时间序列会根据其具体的日期,分入相应的聚类,然后用该类的时间序列异常检测方法来进行异常检测。

Period_Fig6
Period 的核心思路

从上图可以看到 Period 的核心思路(core idea)。在本文使用的数据中,时间序列的长度较长,一般来说都是好几个月到半年不等,甚至更长的时间。对于一条时间序列(a given KPI),可以将它的历史数据(historical data)进行按天切分,获得多个子序列(sub KPIs)。对于这多个子序列,需要进行聚类以得到不同类别。或者按照日历直接把时间序列的工作日(work day),休息日(off day),春节(spring festival)序列进行切分,将工作日放在一起,休息日放在一起,春节放在一起。把这些子序列进行拼接就可以得到三条时间序列数据,分别是原时间序列的工作日序列(work day subsequence),休息日序列(off day subsequence),春节序列(spring festival subsequence)。然后分别对着三条时间序列训练一个异常检测的模型(例如 Holt-Winters 算法,简写为 HW)。对于新来的时间序列,可以根据当日具体的日期(工作日,休息日或者春节)放入相应的模型进行异常检测,从而进一步地得到最终的结果。

在离线周期性检测的技术方案里面,是需要对时间序列进行周期性检测(Periodicity Detection)。而周期性检测有多个方案可以选择。第一种就是周期图方法(Periodogram),另外一种就是自相关函数(Auto-correlation function)。但是在这个场景下,用这些方法就不太合适了。作者们提出了别的解决方案。

在本文中,作者们提出了一种 Shape-based distance(SBD)的方法,针对两条时间序列 X=(x_{1},x_{2},\cdots,x_{m})Y=(y_{1},y_{2},\cdots,y_{m}),提出了相似性的计算方法。

X_{(s)}=\begin{cases}(0,\cdots,0,x_{1},\cdots,x_{m-s}), &\text{ if } s\geq 0 \\ (x_{1-s},x_{1-s+1},\cdots,x_{m},0,\cdots,0), &\text{ else } s<0.\end{cases}

其中 0 的个数都是 |s|. 进一步可以定义,当 s\in[-w,w]\cap\mathbb{Z} 时,

CC_{s}(X,Y)=\begin{cases}\sum_{i=1}^{m-s}x_{i}\cdot y_{s+i}, &\text{ if } s\geq 0 \\ \sum_{i=1}^{m+s}x_{i-s}\cdot y_{i}, &\text{ else } s<0.\end{cases}

于是,选择令 CC_{s}(X,Y) 归一化之后的最大值作为 X,Y 的相似度,i.e.

NCC(X,Y)=\max_{s\in[-w,w]\cap\mathbb{Z}}\frac{CC_{s}(X,Y)}{\|x\|_{2}\cdot\|y\|}.

而基于 SBD 的距离公式则可以定义为:

SBD(X,Y) = 1-NCC(X,Y).

Period_Fig8
Periodicity Drift

那么为什么需要考虑一个漂移量 s 呢,因为在一些实际的情况下,时间序列是会存在漂移的,例如上图所示。该时间序列在 10 月 30 日,31 日,11 月 1 日 都出现了一个凸起,但是如果考虑它的同比图,其实是可以清楚地看出该时间序列就存在了漂移,也就是说并不是在一个固定的时间戳就会出现同样的凸起,而是间隔了一段时间。这就是为什么需要考虑 s 的由来。

Period_Alg1
聚类的命名算法

通过相似性和距离的衡量工具,我们可以将时间序列进行聚类,然后通过上述算法也可以对每一个聚类的结果进行命名。

Period_Table1
实验数据

Period_Table2
实验数据的聚类结果

在本文中,针对以上六条时间序列,作者们做了详细的分析,也对其余的 50 条时间序列进行了实验。其使用的方法包括 HW,TSD,Diff,MA,EWMA,Donut。在 HW 中,针对不同的日期使用了不同的方法,例如 HW-day,HW-week,HW-period;其余的方法也是针对不同的日期来做的。

Period_Table3
实验方法

Period_Table12
实验效果

从实验效果来看,Period 方法的话相对于其他方法有一定的优势。

结论:Period 方法包括两个部分,第一部分是离线周期性检测,第二部分是在线适应性异常检测。通过这样的方法,可以有效地减缓时间序列异常检测受节假日效应的影响。除此之外,想必未来也会有其余学者提出相应的问题和解决方案,敬请期待。

zr9558's Blog