本文记录如何使用tensorflow实现基于transformer的轨迹分类。 在技术实现上包含以下关键细节需要注意： 轨迹点如果超出模型序列长度则进行中间截断，如果不足则进行中间补0 轨迹数据需要对单条数据进行归一化 只使用transformer的encoder部分进行建模，不使用embedding或positional embedding机制，这种方式工程实现简单，但模型可能无法捕获序列前后的区域信息 代码实现 首先实现transformer encoder，内部结构为self-attention和feed forward网络。 def scaled_dot_product_attention(q, k, v, mask=None): matmul_qk = tf.matmul(q, k, transpose_b=True) # (..., seq_len_q, seq_len_k) dk = tf.cast(tf.shape(k)[-1], tf.float32) scaled_attention_logits = matmul_qk / tf.math.sqrt(dk) if mask is not None: scaled_attention_logits += (mask * -1e9) attention_weights = tf.nn.softmax(scaled_attention_logits, axis=-1) # (..., seq_len_q, seq_len_k) output = tf.matmul(attention_weights, v) # (..., seq_len_q, depth_v) return output, attention_weights class MultiHeadAttention(tf.keras.layers.Layer): def __init__(self, d_model, num_heads, dropout): super(MultiHeadAttention, self).

The Big Picture 假如你在没有任何统计数据支撑的情况下，想知道中国的人口地理重心，该怎么办？按照MCMC的观点，应该这样： 随便去一个地方\(x_t\)，数一数方圆1公里的人口数量\(\pi(x_t)\) 再以一定概率从\(x_t\)去另一个地方\(x_\)，数一数人口\(\pi(x_)\)，但只以一定概率\(\alpha\)保留它 重复以上过程很多次，获得很多个旅行记录 以人口为权重，对这些记录的地理位置进行加权求和 这里前3步即MCMC的过程，最后一步是使用样本点对分布参数进行的估计，其中\(\alpha\)可利用Markov的平稳条件得到。 Monte Carlo Monte Carlo模拟简称MC。早期的MC都是用来解决一些不太好解决的求和和积分问题，例如，特定概率密度函数下的期望求解任务。例如： $$ \theta=\int_a^bf(x)dx $$ 这个积分如果难解的话可以使用采样多个点的形式来进行估计： $$ \frac{b-a}{n}\sum^{n-1}_{i=0}f(x_i) $$ 同时，如果\(x\)在\([a,b]\)之间不是均匀的，则需要引入一个\(x\)的概率分布\(p(x)\)，原积分表达式可以写为： $$ \theta=\int_a^bf(x)dx=\int_a^b\frac{f(x)}{p(x)}p(x)dx\approx\frac{1}{n}\sum_{i=1}^{n}\frac{f(x_i)}{p(x_i)} $$ 上述即为MC的一般形式。但这里还有一个问题，即如何根据\(p(x)\)获得基于该分布的\(n\)个\(x\)样本，尤其是如果\(p(x)\)的概率分布非常复杂，那么就需要采用别的手段实现\(x\)的采样，一种可行的方式是接受-拒绝采样。 接受-拒绝采样分为以下步骤： 考虑找到一个方便采样的函数\(q(x)\)，以及一个常量\(k\)，使得\(p(x)\)总在\(kq(x)\)的下方（这里需要进行试算函数\(q(x)\)的具体参数）。 采样\(q(x)\)得到一个样本\(z_1\)。 从均匀分布\((0,kq(z_1))\)中采样得到一个值\(u\)。如果u在图中灰色区域则拒绝样本\(z_1\)，否则则接受。 得到n个接受的样本点为\(z_1,z_2,…z_n\)。 这样MC的最终结果可表示为： $$ \theta \approx \frac{1}{n}\sum_{i=1}^n \frac{f(z_i)}{p(z_i)} $$ 从上面的接受-拒绝采样看，对于一个复杂的\(p(x)\)，想找到一个合适的\(q(x)\)和常数\(k\)是非常困难的，所以有后续使用Markov链进行采样的方法。 MCMC 如果能构造一个转移矩阵为P的马氏链，使得马氏链的平稳分布刚好是p(x)，如果马氏链在第n步开始收敛，那么可以获得\(x_n, x_{n+1}, …\)这些步骤的样本，可作为原始分布的采样。 马尔科夫链的采样过程如下： 输入马尔科夫链的状态转移矩阵\(P\)，设定状态转移次数阈值\(n_1\)，需要样本数\(n_2\)。 从任意简单概率分布采样得到初始状态值\(x_0\)。 重复\(n_1+n_2\)步，从条件概率分布\(P(x|x_t)\)中采样得到样本\(x_t\)，那么后面\(n_2\)个样本即为平稳分布对应的样本集。 但是，对于一个概率平稳分布\(\pi\)，一般是很难找到对应的马尔科夫链的状态转移矩阵\(P\)的。 MCMC正是为了应对上面找不到\(P\)的问题。MCMC先随机选择了一个矩阵\(Q\)，显然，它很难满足细致平稳条件，即有\(\pi(i)Q(i,j)\neq\pi(j)Q(j,i)\)。 MCMC对上式进行了简单的改造，引入了一个\(\alpha(i,j)\)函数，使得： $$ \pi(i)Q(i,j)\alpha(i,j)=\pi(j)Q(j,i)\alpha(j,i) $$ 这样，转移矩阵就有了一个新的表示： $$ P(i,j)=Q(i,j)\alpha(i,j) $$ 其中的\(\alpha(i,j)\)非常类似于接受-拒绝采样中的采样条件，所以被成为接受率。 总的MCMC过程如下： 选定任意一个马尔科夫链状态转移矩阵\(Q\)，平稳分布\(\pi(x)\)，设定状态转移次数阈值\(n_1\)、需要样本个数\(n_2\)。 从任意简单概率分布得到初始状态\(x_0\)。 for t = 1 to \(n_1+n_2\)： 从条件概率分布\(Q(x|x_t)\)中采样得到样本\(x_*\)。 从均匀分布采样\(u\sim\text{uniform}[0,1]\)。 如果\(u<\alpha(x_t,x_)=\pi(x_)Q(x_,x_t)\)，则接受转移\(x_{t+1}=x_\)，否则不接受转移，即\(x_{t+1}=x_{t}\)。 Metropolis-Hastings又对MCMC在循环的第三步进行了改进，原有\(\alpha_{i,j}\)可能是一个非常小的结果，导致绝大多数采样都被拒绝，马尔科夫链的收敛速度会很慢。具体办法是对循环第三步进行了调整，将\(\alpha(i,j)\)的计算调整为： $$ \alpha(x_t,x_)=\min \lbrace\frac{\pi(x_)Q(x_,x_t)}{\pi(x_t)Q(x_t,x_)},1\rbrace $$

此文是oi-wiki中字动态规划部分的总结。 1 要点 2 题目 2.1 入门 最长升序子序列 这个题目使用单调队列复杂度为O(nlogn)，关键点在于序队列维护升序串，同时对于一个更小的输入，在队列中找到稍大于它的元素并进行替换。 帖子中表述有问题，队列中大于更小输入的元素不进行删除。

此文是oi-wiki中字符串部分的总结。 1 要点 前缀函数 前缀数组的第i位pi[i]表示s[0...i-1]的首尾两个子串相同，且子串长度为pi[i]。 前缀数组的递归结构在于，在计算pi[i]时，如果前后两个子串的最后一位j不匹配，并不需要从起始部分重新比较，而是可以利用pi[i]=p[j]直接得到，该式成立的原因在于，0..j和i-j+1..i这两个子串的前后子串四段子串是相等的，导致如果pi[j]满足前缀数组定义，那么第1段与第4段也满足前缀数组定义。 后缀数组 后缀数组包含两个概念，rk[i]表示以位置i为开端的后缀串在数组中字典序的排位，sa[j]表示字典序排序为j的后缀在数组中的位置。 后缀数组可通过倍增法快速求得。 z函数 字符串s的z函数的第i位z[i]是指，第i位开始的子串与原字符串最长的相同前缀的位数。 KMP自动机 KMP算法可用前缀数组直接实现。对于目标串s和输入串t，只需要计算s+#t的前缀数组的最大元素即可。 但这种方式计算KMP有O(|s|+|t|)的空间开销，可使用自动机将开销缩小为O(|s|)。 自动机的构建同样可以利用前缀数组的递归结构。 for (int i = 0; i < n; i++) { for (int c = 0; c < 26; c++) { if (i > 0 && 'a' + c != s[i]) aut[i][c] = aut[pi[i - 1]][c]; // 当前位置失配，利用递归结构向前搜索 else aut[i][c] = i + ('a' + c == s[i]); //当前位置匹配 } } AC自动机 AC自动机是结合了Trie树的多模式匹配的算法。 最简单的情况，使用Trie树进行多模式匹配时需要进行逐字遍历，而AC自动机可以实现对串进行单次遍历实现匹配。 实现的关键点就是找到每个状态下对于所有下个字符的输入的状态转移。 关键代码：

1 简介 Snorkel是deepdive的后续项目，当前在github上很活跃。Snorkel将deepdive中的弱监督的思想进一步完善，使用纯python的形式构成了一套完整弱监督学习框架。 2 安装 由于Snorkel当前还处于开发状态，所以官方的安装教程不能保证在所有机器上都能顺利完成。 官方使用了anaconda作为python支持环境，而这个环境在个人看来存在不少问题（在单位这个win 7机器上异常的慢）。 我直接在一个ubuntu虚拟机内使用了virtualenv和原生python2.7对这套环境进行了安装。 step 1: 部署python virtualenv 为了不污染全局python环境，官方推荐使用conda进行虚拟环境管理，这里使用了virtualenv。 sudo apt install python-pip python-dev essential-utils pip install python-virtualenv cd snorkel virtualenv snorkel_env source snorkel_env/bin/activate 根据官方文档安装依赖，并启用jupyter对应的功能。 pip install numba pip install --requirement python-package-requirement.txt jupyter nbextension enable --py widgetsnbextension --sys-prefix step 2: 配置对虚拟机jupyter notebook的远程连接 jupyter notebook规定远程连接jupyter需要密码。 使用以下命令生成密码的md5序列，放置到jupyter的配置文件中（也可以有其他生成密码的方式）。 jupyter notebook generate-config python -c 'from notebook.auth import passwd; print passwd()' vim ~/.jupyter/jupyter_notebook_config.py 修改生成的jupyter配置文件。 c.NotebookApp.ip = '*' c.NotebookApp.password = u'sha1:bcd259ccf...your hashed password here' c.

0 简介 deepdive是一个具有语言识别能力的信息抽取工具，可用作KBC系统（Knowledge Base Construction）的内核。 也可以理解为是一种Automatic KBC工具。 由于基于语法分析器构建，所以deepdive可通过各类文本规则实现实体间关系的抽取。 deepdive面向异构、海量数据，所以其中涉及一些增量处理的机制。 PaleoDeepdive是基于deepdive的一个例子，用于推测人、地点、组织之间的关系。 deepdive的执行过程可以分为： feature extraction probabilistic knowledge engineering statistical inference and learning 系统结构图如下所示： KBC系统中的四个主要概念： Entity Relationship Mention，一段话中提及到某个实体或者关系了 Relation Mention Deepdive的工作机制分为特征抽取、领域知识集成、监督学习、推理四步。 闲话，Deepdive的作者之一Christopher Re之后创建了一个数据抽取公司Lattice.io，该公司在2017年3月份左右被苹果公司收购，用于改善Siri。 1 安装 1.1 非官方中文版cn_deepdive 项目与文档地址： cn-deepdive DeepDive_Chinese 使用了中文版本cndeepdive，来自openkg.cn。但这个版本已经老化，安装过程中有很多坑。 moreutils无法安装问题。0.58版本失效，直接在deepdive/extern/bundled文件夹下的bundle.conf中禁用了moreutils工具，并在extern/.build中清理了对应的临时文件，之后使用了apt进行了安装。 inference/dimmwitterd.sh中17行对g++版本检测的sed出现了问题，需要按照github上新版修改。 numa.h: No such file or directory，直接安装libnuma-dev 1.2 官方版本 按照官方教程进行配置： ln -s articles-1000.tsv.bz2 input/articles.tsv.bz2 在input目录下有大量可用语料。 deepdive do articles deepdive query '?- articles("5beb863f-26b1-4c2f-ba64-0c3e93e72162", content).' \ format=csv | grep -v '^ 使用Stanford CoreNLP对句子进行标注。包含NER、POS等操作。查询特定文档的分析结果：

1 引子 本文是对Blei等人LDA原始论文的总结。给定大量的文档，如何在无标注的情况下确定每个文档的主题词？LDA(Latent Dirichlet Allocation)是这类主题确定问题的一个成熟的解决方案。LDA最初面向文本挖掘领域，但随后在图像分类、行为识别等领域也得到了应用。LDA是一种典型的非监督模型，模型仅需要输入文档集合的词袋模型，模型可输出每个文档对应的主题，每个主题使用关键词的分布来表示。 2 模型定义 LDA的PGM形式如上，我们认为主题数目有K个，文档有M个， 每个文档中有N个词。其中，\(\alpha\) 是Dirichlet分布的参数，大小为1xK，用于控制生成主题的聚集程度； \(\theta\) 表示一个文档中主题的分布大小为1xK；\(z\)为一个为每个词安排主题的01随机变量，大小为1xK，且只有一个值为1；\(\beta\)为一个多项分布的集合，大小为KxV，其中每一行代表一个主题中，不同词出现的概率；而w代表每个文档中的一个词。 沿着上面的PGM的箭头方向，可以总结出词的生成过程。我们已知了每个文档中的词袋模型\(w\)，为了找到一组合适的主题，需要对分布 \(p(w\vert\alpha,\beta)\) 进行推理。由于该分部中蕴含了隐变量主题\(\theta\) ，所以积分将\(\theta\)积掉。代入Dirichlet分布\(p(\theta\vert\alpha)\)，多项分布\(p(z_n\vert\theta)\)，以及一个单独的概率值\(p(w_n\vert z_n,\beta)\)，可得参数的后验概率形式。以下为完整的推导： $$p(w|\alpha,\beta) = \int p(\theta|\alpha)\prod_{n=1}^N p(w|\theta, \beta) d\theta$$ $$= \int p(\theta|\alpha) (\prod_{n=1}^N \sum_{z_n}p(z_n|\theta)p(w_n|z_n,\beta))$$ $$ = \frac{\Gamma(\sum_i\alpha_i)}{\prod_i{\Gamma(\alpha_i)}}\int(\prod_{i=1}^k\theta_i^{\alpha_i-1})(\prod_{n=1}^N\sum_{i=1}^k\prod_{j=1}^V(\theta_i\beta_{ij})^{w_n^j})d\theta$$ 模型的两个关键参数可以通过多种方法进行求解，即模型训练。 3 模型训练 3.1 变分推理 Blei最初的LDA论文中，使用了变分推理（VB）求解LDA参数。这种方法试图使用一个不受约束的变分分布近似LDA的模型的联合概率。类似的手段可以参见Laplace近似，最经典的应用为使用高斯分布近似Bayesian Logistic Regression中观测的后验分布\(p(w\vert\bf{t})\)。VB个人理解为一种链式的迭代估计框架。使用一个Q函数去近似真实分布函数。 3.2 Gibbs Sampling 优势是便于编程实现。 3.3 比较 变分推理的计算快于基于采样的方法，但可能会收敛到局部最优解。Matthew、Blei等人对于LDA在线学习中对变分推理进行了改进。采样方法更为直观、易于工程实现，且在多数场景下，采样的最终性能会好于变分推理。 4 参考文献 Blei, David. Latent Dirichlet Allocation

0 疑问 这类概率推理问题在没有VB方法的时候都是怎么求解的？ VB的直接好处是什么？ 什么是平均场估计？ 这里的估计方法和概率图中的BP的具体关系？ VB中每一步的模型都是设定好的吗？例如LDA中使用Dirichlet作为后验概率？ LDA中的VB是如何推导的？ 1 引子 本文是PRML第10章部分内容的摘录和总结。在很多概率问题中，如果使用精确求解，那么问题规模与随机变量的个数是指数上升的。以主题模型LDA为例，每个词的生成对应一个随机变量，使用确定性的方法会导致问题规模为\(K^{NM}\)。现有的估计方法包括变分推导、随机模拟/采样、MCMC方法。其中变分推理是一个实现框架，具体而言有Loopy belief propagation方法和Mean field approximation方法。为了简单，以下VB即是说变分推理。 用最简单的话来讲，VB是说数据集中很多特性经过简单统计能反映原始参数的多少，每次迭代我们首先在E步对这些特性进行统计（实际上是求解充分统计量），之后，在M步看在这些统计结果的限制内，参数最可能是多少。这些特性可能是一些计数结果等，例如在LDA模型中，可能是属于不同主题的词的个数等等。有意思的是，在这个角度上VB方法与采样方法有着很大的相似点，唯一不同的是，VB方法每次迭代有明确的前进方向，而采样是靠数量取胜，从这里也能看出VB和采样的优势分别是速度和精度。 2 核心思想 变分推理的最终目的是要找到一个形式简单的分布Q，使得其能较好地估计形式复杂的真实分布P的取值。当我们指定一个Q之后，可以列出Q与P的关系： $$\ln{p(\bf{X})}=\mathcal{L}(q)+KL(q||p)\tag{1}$$ 其中， $$\mathcal{L}(q)=\int{q(Z)\ln{\frac{p(X,Z)}{q(Z)}}dZ}$$ $$KL(q||p)=-\int{q(Z)\ln{\frac{p{(Z|X)}}{q(Z)}}dZ}$$ 这里我们使用KL散度描述P与Q的近似程度。KL散度是似然比的对数期望，它也是确定q之后p的混乱程度。另外，由于因为q与p不同分布时\(KL(p\vert\vert q) \neq KL(q\vert\vert p)\)，所以我们实际上面临\(KL(q\vert\vert p)\)和\(KL(p\vert\vert q)\)两个选择，实际情况是前者更为合理。如果我们能获得\(Z\)的解析形式的关系，那么参照EM方法中迭代求解隐变量的思路，即可求解隐变量的随机分布。VB与EM的最大区别在于VB中不再出现模型参数，取而代之的是随机变量。 2.1 为何使用\(KL(q\vert\vert p)\) \(KL(q\vert\vert p)\)更倾向于使\(q\)去精确拟合\(p\)概率密度为0时的位置，这就导致对于分离的概率密度函数，\(q\)会产生一种聚集效果，即像后两个图一样拟合其中一个分离的分布，而不是像(a)一样试图拟合非0位置，这种行为叫做model-seeking。 2.2 分布Q的合理形式 这种合理形式叫做可分解分布，满足： $$q(Z)=\prod_{i=1}^{M} q_i(Z_i)$$ 使用这种假设的好处是可将原始分布分解为多个较低维度的成分，可简化计算，这种方法在统计物理中被称为平均场方法。回顾公式(1)，我们的VB的最终目标是求一个Q，使得Q与P的KL距离最小，这等价于\(\mathcal{L}(q)\)的最大化。事实上，由(1)式可直接获得如下关系： $$\mathcal{L}(q)=\int{\ln{p(X,Z)}-\sum_{i}{\ln{q_i}}}\prod_{i}{q_i(x_i)}dZ$$ $$=\int q_{j}\ln{\tilde{p}(X,Z_j)dZ_j}-\int{q_j\ln q_j}dZ_j+\text{const}$$ 以上公式是为了获得\(q_j\)和其他\(q\)的关系，以析解得目标(1)的最优解。推导过程中注意积分变量和提出被积变量中的常量。回顾公式(1)，我们令KL散度直接为0使\(\mathcal{L}(q)=\ln(p)\)，可得以下公式： $$\ln{q^\star_{j_{(\bf{Z_j})}}}=\mathbb{E}_{i\neq{j}}\ln{p(\bf{X},\bf{Z})}]+\text{const}\tag{2}$$ 结论就是：为了估计随机变量\(q_j\)的分布，需要对其他所有随机变量的求期望，这样就极小化了KL散度，即使得Q与P更为接近。 3 实例 VB方法具有一个统一的推导求解框架，但对于不同的模型往往会有不同的insight，PRML中也从不同的方向进行了求解。 3.1 二元高斯模型 （待补充） 3.2 混合高斯模型 首先将GMM模型进行贝叶斯化，GMM的生成模型如下： $$\alpha_0 \rightarrow \pi \rightarrow Z \rightarrow X \leftarrow \mu,\Lambda$$ 其中，\(X\)为观测变量，大小为1xN；Z为每个观测变量在不同类别中的归属，使用01表示，大小为是KxN；\(\pi\)为不同类别的权重，大小为1xK；\(\alpha_0\)为决定\(\pi\)形态的超参数，大小为1xK；\(\mu\)和\(\Lambda\)本身为每个正态分量的均值和方差参数。其中，变量间的关系如下： $$p(X|Z,\mu,\Lambda)=\prod_{n=1}^N\prod_{k=1}^K\mathcal{N}(x_n|\mu_k,\Lambda_k^{-1})^{z_{nk}}$$ $$p(Z|\pi) = \prod_{n=1}^{N}\prod_{k=1}^K\pi_{k}^{z_{nk}}$$ $$p(\pi)=\text{Dir}(\pi|\alpha_0)=C(\alpha_0)\prod_{k=1}^K{\pi_k^{\alpha_0-1}}$$ $$p(\mu,\Lambda)=\prod_{k=1}^{K}{\mathcal{N}(\mu_k|m_0,(\beta_0\Lambda_kk)^{-1})\mathcal{W}(\Lambda_k|W_0,v_0)}$$

1 引子 本文涉及EM的使用场景区别、理论推导。以实践的角度，EM方法是一个迭代优化以求解隐变量的方法。本文内容是PRML第九章的缩减。 2 EM用于GMM模型 2.1 极大似然尝试求解GMM参数 以GMM为例，这里先试图使用最大似然估计的方式求解参数： $$p(x|\pi,\mu,\Sigma)=\sum_{k=1}^{K}\pi_{k}\mathcal{N}(x|\mu_{k},\Sigma_{k})$$ 最终目标是求解两部分内容：未观测变量和模型参数。个人理解对于GMM，其未观测变量可明确地指定为\(\pi_{k}\)，而其模型参数确定为\(\mu_k\)和\(\Sigma_k\)。这里优化目标是当前的估计导致的损失，或者说对数似然函数： $$\ln{p(X|\pi,\mu,\Sigma)}=\sum_{n=1}^{N}{\ln\sum_{k=1}^K{\pi_k\mathcal{N}(x_n|\mu_k,\Sigma_k)}}$$ 以上问题由于隐变量的存在，同时由于参数在正态分布的积分中，一般来说是难解的。具体地，对\(\ln{p(X|\pi,\mu,\Sigma)}\)求导，并令导数为0可以看出隐变量和参数之间的关系： $$\frac{\partial{\ln{p(X|\pi,\mu,\Sigma)}}}{\partial{\mu_k}}=-\sum_{n=1}^{N} \gamma(z_{nk})\Sigma_k(x_n-\mu_k)=0$$ $$\frac{\partial{\ln{p(X|\pi,\mu,\Sigma)}}}{\partial{\Sigma_k}} =\sum_{n=1}^N \gamma(z_{nk}) {-\frac{N}{2}\Sigma^{-1}+\frac{N}{2}\Sigma^{-1}\sum_{d=1}^{D}(x_i-\mu)^T \Sigma^{-1}k (x_i-\mu)\Sigma^{-1}}=0$$ 其中，\(\gamma(z{nk})\)的物理意义是第n个观测在第k簇的概率，形式为： $$\gamma(z_{nk})=\frac{\pi_k\mathcal{N}(x_n|\mu_k,\Sigma_k)}{\sum_j{\pi_j\mathcal{N}(x_n|\mu_j,\Sigma_j)}}$$ 具体的结果可参考PRML。使用以上两个等式，原则上可计算参数和未观测量的值，这里是为了展现：由于对数中本身有加和的形式，这种方式难以获得解析解。需要有一个更便捷的框架解决以上参数求解问题。 2.2 EM方法估计GMM参数 EM方法正是这样一个框架：套用以上的结果，使用迭代的方法通过不断修正找到一个函数\(q(x)\) ，使得\(q(x)\)与\(p(x)\)接近，那么即可使用\(q(x)\)对最终结果进行近似。具体的步骤如下： 初始化参数\(\mu_k\)、\(\Sigma_k\)和未观测值\(\pi_k\)。一个可行的方式是，由于K-means迭代次数较快，可使用K-means对数据进行预处理，然后选择K-means的中心点作为\(\mu_k\)的初值。 E步，固定模型参数，优化未观测变量： $$\gamma(z_{nk})=\frac{\pi_k\mathcal{N}(x_n|\mu_k,\Sigma_k)}{\sum_j{\pi_j\mathcal{N}(x_n|\mu_j,\Sigma_j)}}$$ M步，M步将固定未观测变量，优化模型参数： $$\mu_k^{new}=\frac{1}{N_k}\sum_{n=1}^{N}\gamma(z_{nk})\bf{x}n$$ $$\Sigma_k^{new}=\frac{1}{N_k}\sum{n=1}^{N}\gamma(z_{nk})(\bf{x}_n-\mu_k^{new})(\bf{x}_n-\mu_k^{new})^T$$ 计算likehood，如果结果收敛则停止。 3 EM方法正确性 （待续）

1 简介 Nimbits是一个专门针对物联网设计的数据汇集平台。该平台使用嵌入的hsql作为数据存储，使用Java作为编程语言，运行于Web环境中。相对于现有的Google/IBM 等公司的用于IoT的云平台，该平台简单、灵活、高度可定制，可为小型IoT业务提供了一套完整的数据解决方案。本文将介绍如何在本地搭建Appscale集群，并于之上部署Nimbits。 2 运行环境搭建 需要先后安装Virtual Box、Vagrant、Appscale。安装流程解释请参照 fast-install和Appscale wiki。 2.1 安装VirtualBox和Vagrant VirtualBox提供虚拟机运行环境，Vargrant提供虚拟机配置的复制和分离运行，类似于Docker的雏形。在安装Vargrant插件时，可能会出现删除VirtualBox的警告，可直接忽视。安装完成之后需要建立Vagrantfile，该文件用于指定虚拟机初始化内存、IP等配置信息。使用vagrant up命令启动vagrant虚拟机，使用vagrant ssh命令与vagrant虚拟机进行ssh通讯。 2.2 安装Appscale服务 Appscale是类似于Google App Engine的一个分布式应用运行平台。目标搭建的服务分别部署于本机和虚拟机集群。首先，下载基于Ubuntu 12.04的Appscale镜像，可使用wget和aria2c从备用地址加速镜像下载过程。该镜像已经包含集群环境。其次，在本地安装Appscale工具。使用命令appscale init cluster启动集群，使用命令appscale up启动控制服务。使用appscale clean和appscale down分别可清除部署和停止服务。启动服务时，可能出现如下问题： stacktrace : Traceback (most recent call last): File "/usr/local/appscale-tools/bin/appscale", line 57, in appscale.up() File "/usr/local/appscale-tools/bin/../lib/appscale.py", line 250, in up AppScaleTools.run_instances(options) File "/usr/local/appscale-tools/bin/../lib/appscale_tools.py", line 362, in run_instances node_layout) File "/usr/local/appscale-tools/bin/../lib/remote_helper.py", line 202, in start_head_node raise AppControllerException(message) ... 根据这个讨论，关闭所有的Python、Java和Ruby程序可以修复该问题。 2.3 在集群环境下部署Nimbits 本地使用环境为Ubuntu 12.04、mysql 5.5、Java 7。启动之后可访问以下API进行测试，Nimbits会对应返回系统时间。 http://localhost:8080/nimbits/service/v2/time。 3.