社区发现及其发展方向简介(未完)

1. 社区发现简介

社区,从直观上来看,是指网络中的一些密集群体,每个社区内部的结点间的联系相对紧密,但是各个社区之间的连接相对来说却比较稀疏(图1,当然社区的定义不止有这一种)。这样的社区现象被研究已经很多年了,最早期的记录甚至来自于80年前。

aaa

比较经典的社区研究案例包括对空手道俱乐部(karate club),科学家合作网络(Collaboration network) 和斑马群体(zebras) 的社交行为研究等(见图2),其中著名的空手道俱乐部社区已经成为通常检验社区发现算法效果的标准(benchmark)之一。

Read More

LDA学习笔记---来自《Parameter estimation for text analysis》

2013年10月10日更新。

LDA的概率图如下图1所示:QQ截图20130312094645

参数的意思如图2所示:

QQ截图20130312094711 根据模型,文章m的第n个词t是这样生成的:先从文章m的doc-topic分布中生成一个topic编号\(z_{m,n}\),在根据编号第\(z_{m,n}\)个的topic-word分布中生成这个词,总够有\(K\)个topic,所以总的概率为: \[ p(w_{m,n}=t|\vec{\theta}_m,\underline{\Phi})=\sum^K_{k=1}p(w_{m,n}=t|\vec{\phi}_k)p(z_{m,n}=k|\vec{\theta}_m)\] 如果我们写出这篇文章的complete-data的联合分布(意思就是所以变量都已知的情况下),那么式子就是这样的:

QQ截图20130312094748

通过对\(\vec{\vartheta_m}\)(doc-topic分布)和\(\underline{\Phi}\)(topic-word分布)积分以及\(z_{m,n}\)求和,我们可以求得\(\vec{w_m}\)的边缘分布:

QQ截图20130312094757

(实际上这个边缘分布是求不出来的,因为\(z_{m,n}\)是隐藏变量,从而导致\(\underline{\vartheta}\)\(\underline{\Phi}\)存在耦合现象,无法积分得到。要注意联合分布和边缘分布对Z乘积与加和的区别)

因为一个语料库有很多篇文章,而且文章之间都是相互独立的,所以整个语料库的似然为 \[ p(\mathcal{W}|\vec{\alpha},\vec{\beta})=\prod^{M}_{m=1}p(\vec{w_m}|\vec{\alpha},\vec{\beta})\]

虽然LDA(latent Dirichlet allocation)是个相对简单的模型,对它直接推断一般也是不可行的,所以我们要采用近似推断的方法,比如Gibbs sampling。

Read More

有趣的三门问题(蒙提霍尔问题)

三门问题(Monty Hall problem),是一个源自博弈论的数学游戏问题,大致出自美国的电视游戏节目Let’s Make a Deal。问题的名字来自该节目的主持人蒙提·霍尔(Monty Hall)。问题非常的有意思^_^,给出叙述如下:

在三扇门中的某扇门以后有一个奖品,选中这扇门就能拿到门后的奖品。你选定了一扇门,具体地说,假设你选择了1号门。这时候主持人蒙提·霍尔会打开剩下两扇门的其中一扇,你看到门后没有奖品。这时候他给你一个机会选择要不要换另外一扇没有打开的门。你是选择换还是不换呢?

答:因为我之前就选了,换或者不换机会都是均等的,所以换不换无关紧要╮(╯▽╰)╭。 ↓ ↓ ↓ ↓ ↓ ↓ ↓ ↓ ↓ ↓ 真的是这样么?仔细分析一下,游戏过程中你做了2个操作: 第一,你选择了一扇门。第二,你选择了换门或者不换。 定义事件\(A\)为你第一次就选中奖品。 定义事件\(B\)为你换门选中奖品。 那么\(A^c\)为集合A的余集,即第一次没有选中奖品。同理,\(B^c\)为换门没有选中奖品。整个游戏过程中,\(A\)\(A^c\)先发生,\(B\)\(B^c\)再发生。 显而易见的是 \[P(A)=1/3,P(A^c)=2/3\] 要注意的是,在第一次操作之后,还有一件事——主持人打开了一扇没有奖品的门。值得注意的是,这里主持人的动作是跟你第一次选择有关系的:

  1. 如果你一开始就选中了奖品,即事件\(A\)发生了,那么他就在剩下的两扇没有奖品的门之间任选一门打开。接下来,如果你选择换门,那么抽中的概率为0,不换抽中的概率为1。 即 \[P(B|A)=0,P(B^c|A)=1\] 因为事件\(B\)\(B^c\)是在事件A发生之后发生的,所以这里的概率是基于事件\(A\)的条件概率。

  2. 如果你开始没有选中奖品,即事件\(A^c\)发生了,那么他只能打开另一扇没有奖品的门。这时候,如果你选择换门,那么抽中的概率为1,不换抽中的概率为0。 即 \[P(B|A^c)=1,P(B^c|A^c)=0\] 这里的概率是基于事件\(A^c\)的条件概率。

由上我们可以发现一点,事件\(A\)会影响事件\(B\)的概率,即事件\(A\)和事件\(B\)并不是相互独立的。\(A^c\)\(B^c\)也是同理。 于是,利用全概率公式,我们可以求得换门选中奖品的概率为 \[P(B)=P(B|A)P(A)+P(B|A^c)P(A^c)=0*1/3+1*2/3=2/3\] \[P(B^c)=P(B^c|A)P(A)+P(B^c|A^c)P(A^c)=1*1/3+0*2/3=1/3\] 所以事实上你换门能得到奖品的概率为2/3,是不换门的2倍(懂点数学真好啊)。是不是和直觉不太一样?个人认为,直观上觉得\(P(B)=1/2\)的原因是忽略了第一次选择时,通过主持人的动作改变了换门的事件概率这一客观过程。 2013年7月3日更新
从信息论的角度来说,B事件的熵为H(B),在A事件发生之后B事件的条件熵为H(B|A),可以证明 \[H(B) \geq H(B|A) \] 也就是说,在给予了A的信息之后,B的不确定性下降了。