社区，从直观上来看，是指网络中的一些密集群体，每个社区内部的结点间的联系相对紧密，但是各个社区之间的连接相对来说却比较稀疏（图1，当然社区的定义不止有这一种）。这样的社区现象被研究已经很多年了，最早期的记录甚至来自于80年前。
比较经典的社区研究案例包括对空手道俱乐部(karate club),科学家合作网络(Collaboration network) 和斑马群体(zebras) 的社交行为研究等（见图2），其中著名的空手道俱乐部社区已经成为通常检验社区发现算法效果的标准(benchmark)之一。
2013年10月10日更新。
LDA的概率图如下图1所示：
参数的意思如图2所示：
根据模型，文章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的联合分布（意思就是所以变量都已知的情况下），那么式子就是这样的：
通过对\(\vec{\vartheta_m}\)（doc-topic分布）和\(\underline{\Phi}\)（topic-word分布）积分以及\(z_{m,n}\)求和，我们可以求得\(\vec{w_m}\)的边缘分布：
(实际上这个边缘分布是求不出来的，因为\(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。
聚类分析将数据划分成有意义的簇，如果目标是划分成有意义的组，则簇应当捕获数据的自然结构。 聚类的目的可以分为2类：
旨在理解的聚类。比如生物学，信息检索，气候模式，心理学和医学，商业等。
旨在实用的聚类。旨在汇总数据，压缩数据，有效地发现最近邻。
关联分析是一种发现隐藏在大型数据集中有意义的数据联系的方法。所发现的联系可以用关联规则或者频繁项集的形式表示,比如以下规则： \[\{nappy\}\rightarrow\{beer\}\] 该规则表明尿布和啤酒的销售之间存在很强的联系，因为许多购买尿布的顾客也买啤酒。
分类任务就是通过学习得到一个目标函数(target function)\(f\),把每个属性集\(x\)映射到一个预先定义的类标号\(y\)。 分类和回归的区别之处就是类标号是否是离散的。回归的目标属性\(y\)是连续的。 分类的一般方法有决策树，基于规则的分类，神经网络，支持向量机和朴素贝叶斯算法。
（改动中-2014年1月24日）
先给出一般EM算法的问题定义。 给定一个训练集\(X=\{x^{\{1\}},\ldots,x^{\{m\}}\}\)。根据模型的假设，我们希望能够通过这些数据来估计参数\(\theta\)，但是每个我们观察到的\(x^{i}\) 还受着一个我们观察不到的隐含变量\(z^{i}\)（也是\(\theta\)生成的）控制，我们记\(Z=\{z^{\{1\}},\ldots,z^{\{m\}}\}\), 整个模型\(p(X,Z|\theta)\)是个关于变量\(X,Z\)的联合分布。
我们通过求最大似然\(L(\theta|X)\)来估计\(\theta\)的值。
\[ \theta=\arg\max_{\theta} L(\theta|X)\]
其中
\[ L(\theta|X)=\ln p(X|\theta)=\ln \sum_{Z}{p(X,Z|\theta)}\]
这里要注意\(p(X|\theta)\)是一个边缘分布，需要通过聚合\(Z\)得到。由于右边的式子在对数函数中又存在加和，所以我们直接对似然求导是没办法得到\(\theta\)的。
这里EM算法可以比较好地解决这个问题。对于EM的一般算法，有从期望的角度解释，用Jensen不等式证明正确性的方法（见参考2）。这里我讲的是另一种从相对熵角度解释，来自PRML的方法。这两种方法各有特定，对比如下：
使用期望的角度来讲，可以地了解EM算法是如何绕过未知\(Z\)下难以计算的问题，即通过最大化它的期望。但是对E和M步如何逼近极大似然的过程，需要对Jensen不等式和单调逼近\(\theta\)最优值过程的理解。
使用相对熵角度解释，可以看清似然函数和它的下界函的迭代增长过程。但是对\(Q(Z)\)和KL散度的引入，以及为什么要最大化下界函数这一点讲的不是很明白（个人看法）。2013年9月25日更新：这里应该是设一个分布Q(z)来近似P(Z)，KL散度描述了这两个分布之间的差异，这里只是没有提到下界函数刚好是似然关于后验概率的期望，要求的是下界函数也就是期望的最大值。
这周主要学习了高斯混合模型以及EM算法的经典应用。Gaussian Mixture Model (GMM)即可以用于聚类，也可以用于估计概率密度函数。假设我们有一个训练集\(x^{(1)},\ldots,x^{(m)}\), 这训练集是无监督的，所以没有分类标签。
多项分布是二项分布的推广。二项分布（也叫伯努利分布）的典型例子是扔硬币，硬币正面朝上概率为\(p\), 重复扔\(n\)次硬币，\(k\)次为正面的概率即为一个二项分布概率。而多项分布就像扔骰子，有6个面对应6个不同的点数。二项分布时事件\(X\)只有2种取值，而多项分布的\(X\)有多种取值，多项分布的概率公式为 \[P(X_{1}=x_1,\cdots ,X_{k}=x_{k})= \begin{cases}&\frac{n!}{x_{1}!,\cdots,x_{k}!}p^{x_{1}}\cdots p^{x_{k}}\quad \textrm{when}\sum^{k}_{i=1}{x_{i}=n}\\&0 \qquad\qquad\qquad\qquad\qquad\;\textrm{otherwise.} \end{cases}\] 这个公式看上去像是莫名其妙地冒出来的，想要了解它首先必须要知道组合数学中的多项式定理。
多项式定理：当\(n\)是一个正整数时,我们有 \[(x_{1}+x_{2}+\ldots+x_{k})^n=\sum{\frac{n!}{r_1!r_2!\cdots r_k!}x_1^{r_1}\ldots x_k^{r_k}}\] 其中\(r_1+ \ldots + r_k=n,r_i \geq 0\)。