高斯混合模型(GMM, Gaussian Mixture Model)是混合模型的一种，它可以和k-means算法一样用于聚类，但k-means是把数据直接划分到某个cluster，而GMM则可以进一步给出该数据点可以被划分到该cluster的概率。 给定 $N$ 个训练样本 $\brace{x^{(1)},\dots,x^{(N)}}$ 。同样，假设样本集合可以被分成 $K$ 类(又称component)，即 $x^{(i)}$ 分到相应类别 $z^{(i)} \in \brace{1,\dots,K}$ ，并且样本属于某个类别的概率服从多项式分布 $z^{(i)} \sim Multinomial(\phi)$ ，其中 $p(z^{(i)}=j)=\phi_j, \phi_j \geq 0, \sum_{j=1}^K \phi_j=1$ ；而每个类别里的样本分布服从高斯分布 $x^{(i)}\vert z^{(i)}=j \sim \mathcal{N}(\mu_j, \Sigma_j)$ 。由于各个类别里的样本分布可以表示为 $p(x^{(i)},z^{(i)}) = p(z ...

k-means可能是最简单的一种聚类方法，它通常也被当作一种基准方法，用于比较其他聚类方法的性能。它的基本思想是假定数据分布为k个簇(cluster)；所以，先随机或者按照某种启发式方法选择k个质心(cluster centroids)作为起始簇，然后为每个数据点寻找距离最近的质心，并把它分配(assign)给该质心对应的簇，处理完所有数据点后，重新给这k个簇更新质心到该簇所有点的平均值；然后，不断迭代，直到质心稳定不变。 这里我们给定 $N$ 个样本 $\brace{x^1,\dots,x^N}$ ，算法步骤如下： 随机初始化 $K$ 个质心 $\mu_1,\dots,\mu_K \in \Re^n$ ； 重复下面的步骤，直到收敛。 (1) 对每个样本 $i$ ，计算其应该属于的类： \[c^i := \operatorname*{arg\,min}_j \Abs{x^i - \mu_j}^2\] (2) 对每个类 $j$ ，重新计算该类的质心： \[\mu_j := {\sum_{i=1}^N \mathrm{sign}(c^i=j ...

如果想要在web上嵌入视频播放，也就是通过各种浏览器来看视频，我觉得HTML5已经是大势所趋。至少从码农的角度来看是个相对完美的方案，在以前浏览器对视频的支持没有标准，所以往常在浏览器上看到的视频并非由浏览器驱动，而是由一堆混乱的第三方插件来支持的，比如flash、realplayer、quicktime等等解决方案。所以，我们经常看到视频边框有各家的标识，常常你没有安装某个插件，视频就播放不了，这对用户就很不友好了。但现在由于移动端的开拓，教主直接拍死了flash，HTML5给出了视频标准（统一的<video>标签），同时各大主流浏览器也争先恐后的开始支持HTML5，种种合力给web视频播放推向一个好的未来。我们从各大视频网站youtube、youku对移动设备的支持就可以看出来。 然而，如果我们想把一段视频放到网站，或者说你想开发另一个youtube（当然是不可能的），整个流程该怎么做呢？本文很多内容学习自Dive into html5视频这一章，感兴趣的也可自行翻阅。 视频 两个概念：container 和 codec 容器(container) 我们经常听人 ...

$\newcommand{\A}{\mat{A}} \newcommand{\U}{\mat{U}} \newcommand{\V}{\mat{V}} \newcommand{\S}{\mat{\Sigma}}$ 奇异值分解 令 $r$ 是 $M \times N$ 的矩阵 $\A$ 的秩； $\U$ 是 $M \times M$ 矩阵，列是 $\A\A\tr$ 的正交特征向量； $\V$ 是 $N \times N$ 矩阵，列是 $\A\tr\A$ 的正交特征向量；那么 $\A$ 存在如下的奇异值分解(SVD)： \[\A = \U \S \V\tr\] 其中， $\A\A\tr$ 和 $\A\tr\A$ 的特征值相同，均是 $\lambda_1,\dots,\lambda_r$ 。把特征值从大到小排序 $\lambda_i \geq \lambda_{i+1}$ ，对 $1 \leq i \leq r$ ，令 $\sigma_i = \sqrt{\lambda_i}$ ，则中间的 $M \times N$ 矩阵 $\S$ ，满足对角线元素 $\Sigma_{ii} ...

$\newcommand{\cov}{\operatorname{cov}} \newcommand{\var}{\operatorname{var}} \newcommand{\A}{\mathbf{A}} \newcommand{\L}{\mathbf{\Lambda}} \newcommand{\l}{\mathbf{\lambda}} \newcommand{\I}{\mathbf{I}} \newcommand{\S}{\mathbf{S}} \newcommand{\Q}{\mathbf{Q}}$ 协方差矩阵 协方差(Covariance)用于衡量两个变量的总体误差。设两个随机变量 $X$ 和 $Y$ 的期望值分别为 $E(X)$ 和 $E(Y)$ ，则其协方差定义为： \[\cov(X, Y) = E((X - E(X)) (Y - E(Y)))\] 方差是协方差的一种特殊情况，即当两个变量是相同时： \[\var(X) = \operatorname{cov}(X, X) = E((X - E(X))^2)\] 协方差从随机标量推广到随机向量，则得到协方差 ...

\[\newcommand{\x}{\mathrm{x}}\] 论文：Greedy Function Approximation: A Gradient Boosting Machine (Jerome H. Friedman, 1999) Gradient Boosing是一个算法框架，论文在这个框架下实现了多种算法。 代码：https://code.google.com/p/simple-gbdt 参考：A Gentle Introduction to Gradient Boosting (slides) square loss -> gradient descent 参考：http://blog.csdn.net/a819825294/article/details/51188740 前向分布算法+loss函数导出GBDT算法，以及MPI并行化方法。 决策树的节点分裂都是遍历各个feature的各个阈值，但分裂条件有区别： 分类树：Info Gain, Gini 回归树：MSE, Gradient DT优点：non-parametric，不用 ...

Boosting算法基于如下理论： 在概率近似正确学习(probably approximately correct, PAC)的框架中，一个概念，如果存在一个多项式的学习算法能够学习它，并且正确率很高，那么称这个概念是强可学习的；一个概念，如果存在一个多项式的学习算法能够学习它，并且正确率仅比随机猜测略好，那么称这个概念是强可学习的。在PAC框架中，强可学习与弱可学习是等价的。 这意味着在学习中，如果已经发现了“弱学习算法”，那么可以提升(boost)为“强学习算法”。其中需要解决两个问题： 如何在每轮弱分类器的学习中改变训练数据的权值，即改变样本的概率分布； 如果将弱分类器组合成一个强分类器。 adaboost adaboost(Adaptive Boosting)算法表述如下： 输入：训练数据集 $T={(x_1,y_1),\dots,(x_N,y_N)}$ ，其中 $x_i \in \mathcal{X} \subseteq \Re^n$ ， $y_i \in \mathcal{Y} = {-1, 1}$ ； 输出：分类器 $G(x)$ 。 ( ...

拉格朗日乘子法(Lagrange Multiplier)和KKT(Karush-Kuhn-Tucker)条件是求解约束优化问题的重要方法，在有等式约束时使用拉格朗日乘子法，在有不等约束时使用KKT条件。前提是：只有当目标函数为凸函数时，使用这两种方法才保证求得的是最优解。 $\newcommand{\R}{\mathbb{R}}$ 凸函数 如果$f(X)$是定义在$N$维向量空间上的实值函数，对在$f(X)$的定义域$\R^N$上的任意两点$X_1$和$X_2$，以及任意$[0,1]$之间的值$t$都有： \[f(tX_1 + (1-t)X_2) \geq tf(X_1)+(1-t)f(X_2), \quad \forall X_1,X_2 \in \R^N, 0\leq t\leq 1\] 那么称 $f(X)$ 是凸函数。如果去掉等于的情况，则是严格凸函数（Strict Convex）。 三种凸优化问题：无约束优化、等式约束优化和不等式约束优化。 针对无约束最优化问题，通常做法就是对$f(X)$求导，并令$\frac{\partial f(X)}{\part ...

[TOC] \[\newcommand{\x}{\mathbf{x}} \newcommand{\R}{\mathbb{R}} \newcommand{\g}{\mathbf{g}} \newcommand{\H}{\mathit{H}} \newcommand{\d}{\mathbf{d}} \newcommand{\s}{\mathbf{s}} \newcommand{\y}{\mathbf{y}} \newcommand{\T}{\mathsf{T}}\] 考虑无约束最优化问题： \[\min_\x f(\x)\] 其中，$\x=(x_1,x_2,\dots,x_N)^\T \in \R^N$，假设目标函数 $f: \R^N\to \R$为凸函数，且二阶连续可微。 牛顿法 先考虑 $N=1$ 的情况（此时目标函数为$f(x)$）。牛顿法的基本思想是：在现有极小点估计值的附近对$f(x)$做二阶泰勒展开，进而找到极小点的下一个估计值。 设 $x_k$ 为当前的极小点估计值，则 \[\varphi(x) = f(x_k) + f'(x_k)(x-x_k) +\fra ...

[TOC] \[\newcommand{\T}{\mathsf{T}} \newcommand{\X}{\boldsymbol{X}} \newcommand{\x}{\boldsymbol{x}} \newcommand{\y}{\boldsymbol{y}} \newcommand{\W}{\boldsymbol{\theta}} \newcommand{\tr}{\mathrm{tr}}\] Batch GD、mini-batch GD、SGD、online GD的区别在于更新一次参数所用到训练数据： / batch mini-batch Stochastic Online 训练集 固定 固定 固定 实时更新 单次迭代样本数 整个训练集 训练集的子集 单个样本 根据具体算法定 算法复杂度 ...