无监督学习

聚类

聚类的几种常用方法：K-means，Hierarchical Agglomerative Clustering(HAC)。

K-means需要事先决定有K个cluster，每个cluster初始的center也要从training data中随机找k个出来。

Hierarchical Agglomerative Clustering(HAC)就是建树，对每个data两两计算相似度，挑出最相似的一对data，merge成一个新的data vector。一直从下至上构建出root。要分类就是在每一层切一刀获得一种聚类方式。

Dimension Reduction降维

降维的本质就是需要找一个function，当我们input一个vector x的时候，output是另外一个vector z，且output dimension小于input dimension。

特征选择

把data的分布拿出来看一下，发现都集中在某个特定的dimension，那么就拿掉其他dimension就可以。但问题是很多时候任何一个dimension都不能拿掉。

Principal Component Analysis 主成分分析

一维

需要reduce to 1-D，就是要矩阵中的每一行的data points 投影到，然后就可以得到对应的，不同的 投影过后都是相同的。这里的就是的第一行。

该如和确定这个？我们希望投影后所有点之间的奇异度越高越好，对应到数学上就是的方差越大越好。

$$Var(z_1) = \sum_{z_1}(z_1-\bar{z}_1)^2 \quad \left\|w^1\right\|_2=1$$

高维

现在想要投影到一个二位平面，除了把矩阵中的每一行的data points 投影到，还要把矩阵中的每一行的data points 投影到，这里的是的第一行和第二行。

除了基向量的模为1的约束条件，还需要基向量之间是垂直的，代表基向量之间正交。因而可以说是一个正交矩阵orthogonal matrix。

如何寻找正交基

的寻找

$$\begin{split} Var(z_1) &= \frac{1}{N}\sum_{z_1}(z_1-\bar{z}_1)^2 \\ &= \frac{1}{N}\sum_{x}(w^1\cdot x-w^1\cdot\bar{x})^2 \\ &= \frac{1}{N}\sum_{x}(w^1\cdot(x-\bar{x}))^2 \end{split}$$

向量内积可以和矩阵乘法转换（第一个等式），scalar做Transpose之后仍然是一个scalar（最后一个等式），获得如下式子：

$$(a\cdot b)^2 = (a^Tb)^2 = a^Tba^Tb=a^Tb(a^Tb)^T=a^Tbb^Ta$$

带入原方程得到

$$\begin{split} Var(z_1) &= \frac{1}{N}\sum_{x}(w^1\cdot(x-\bar{x}))^2\\ &= \frac{1}{N}\sum_{x} (w^1)^T(x-\bar{x})(x-\bar{x})^Tw^1 \\ &= (w^1)^T \frac{1}{N}\sum_{x}(x-\bar{x})(x-\bar{x})^T w^1 \\ &= (w^1)^T Cov(x) w^1 \quad S = Cov(x) \end{split}$$

也就是说我们需要找的就是能够让最大，且满足约束条件的向量。约束条件是为了保证解出来的vector存在有限个。

运用Lagrange Multiplier拉格朗日数乘法

$$g(w^1) = (w^1)^T S w^1 - \alpha((w^1)^Tw^1-1)$$

对这个式子求偏导数，得到

$$Sw^1 = \alpha w^1 \\ (w^1)^TSw^1 = \alpha (w^1)^Tw^1 = \alpha$$

意思就是是协方差矩阵的特征向量，且它是对应到最大的特征值的那个特征向量。

的寻找

有两个约束条件，因而拉格朗日数乘法的对象如下

$$g(w^2) = (w^2)^T S w^2 - \alpha((w^2)^Tw^2-1) - \beta((w^2)^Tw^1-0)$$

对这个式子求偏导数，再同时乘以，得到

$$\begin{aligned} S w^2 - \alpha w^2 - \beta w^1 = 0 \\ (w^1)^T S w^2 - (w^1)^T \alpha w^2 - (w^1)^T \beta w^1 = 0 \\ ((w^1)^T S w^2)^T -\alpha \cdot 0 - \beta \cdot 1 = 0 \\ \beta = ((w^1)^T S w^2)^T = (w^2)^TSw^1= (w^2)^T \lambda_1 w^1 = 0 \end{aligned}$$

上面的推导表明，那么最初的式子就可以写成

$$Sw^2=\alpha w^2$$

意思就是是协方差矩阵的第二大的特征向量，且它是对应到最第二大的特征值的那个特征向量。

投影后数据的特征

投影和的数据在新的坐标的各个维度之间是不相关的，在数学上的表示就是投影后的的协方差矩阵是一个对角矩阵diagonal matrix。好处是实现模型的时候可以减少参数。

从另一个角度理解PCA

一个输入input可以看作是有限个component的线性叠加加上所有input的平均值。

$$\begin{array}{ll} x = \bar{x} + \hat{x} \\ \hat{x} = c_1u^1+c_2u^2+ \cdots+c_Ku^K \end{array}$$

Reconstruction error:

Find minimizing the error

$$L = min_{\{u^1, u^2 \cdots, u^k\}}\sum\left\|(x-\bar{x}) -(\sum_{k=1}^K{c_ku^k})\right\|_2$$

这里要找的就是对应前面PCA中的。但是这两者有有不同，因为前面PCA要求必须垂直（线性情况较快），但此处用gradient descent求解出来的对象不一定保证垂直（但是可以deep）。

PCA looks like a neuron network with one hidden layer(linear activation function).

PCA involves adding up and substracting some components, and then the componets may not be part of the input. 也就说是用PCA解得得结果不一定是直观上我们可以理解的东西，为了让eigen vector直观化，需要使用Non-negative matrix factorization（NMF），要么让线性叠加的系数为正，要们让线性叠加的子部component为正。

弱点

有可能把两个class都放到一个vector上去。需要用到Linear Discriminant Analysis。

只适用于线性。

矩阵分解 Matrix Factorization

推荐系统中，通常我们只会得到一个作为评分结果的矩阵MXN，这个矩阵是两个矩阵（用户-特性矩阵和特性-物品矩阵）通过某些factor作用的结果。如果这个MXN的矩阵中有缺省内容，如何通过已有信息预测空缺项？

用户维度为M，物品维度为N，特性维度就是latent factor的数目假设为是K。我们希望找到MXK，和KXN的矩阵，让他们相乘之后的结果与评分矩阵MXN最接近，需要minimize error。

对于损失函数的定义如下：Minimizing

$$L = \sum_{(i,j)}{(r^i\cdot r^j-n_{ij})^2}$$

Only considering the defined value and find by gradient descent.

当然也可以在loss function中添加偏置项，更多其他与i有关的scale和与j有关的scale。

Word-embedding词嵌入

为什么需要词嵌入？

传统的表示一个文字的方法就是1-of-N encoding，每一个word用一个vector来表示，这个vector的dimension就是这个世界上可能有的word的数目，很显然这过于大了。但是词汇之间是有联系的，可以组成word class，因此可以把同样性质但是不同的word用所属的class来表示。

词嵌入就是把每一个词都project到high dimension space上去，在这个高维空间中每一个word embedding都有一个feature vector。

如何找到适合该词的词嵌入？了解一个词汇的含义需要看该词的contex。

count-based

基于计数的词嵌入原则是单词的word vector是，单词的word vector是，计算出这两个word vector的inner product后我们希望该值和两个词在该文章中同时出现的次数越近越好。其实这个思想和matrix factorization类似。

prediction-based

预测结构

最朴素的就是拿前一个词汇去预测后一个词汇，也可以用前后词汇预测中间词汇，也可以用中间词汇预测前后词汇。

输入输出定义

希望同class的多个先后连续的词作输入的时候，输出是预测的下一个词汇。为了实现这个效果，中间hidden layer需要通过weight对输入进行转化，让他们对应到相同的空间

input是1-of-N encoding of the word $w{i-2}, w{i-1}$（需要把这两个列向量接在一起变成一个很长的vector放到neuron network中去，有点像CNN中的Flatten）。

output是the probability for each word as the next word 。

需要注意的是，两个vector对应的维度上对应到neuron network中的同一个neuron的weight是一样的（sharing parameters）。

如何训练

为了让$weight{z_1}^{i-2}(1)weight{z_2}^{i-1}(1)$最终迭代结果相同，一开始就需要赋予相同的初始值，且在更新参数的时候，二者的更新表达式相同，除了Cross Entropy对自己的微分，还要算上Cross Entropy对另外一个权重的微分。

多语言与多领域

需要事先知道某几对英文单词和中文单词的对应关系，把这个当作输入放到model中去learn，这个训练好的model的功能就是如何把未知的新的中文和英文对应的词汇放到一起，并投射到空间上的同一个点。

同样的英文和中文单词的对应可以转换成单词和图像的对应关系。

Neighbour Embedding

data point可能是在高维空间中的一个manifold，实际上这笔数据完全可以放到低维空间来描述。高维空间中的问题在于如何描述两个数据的距离/相似度，用欧氏距离没有意义。

因而需要manifold learning把高维空间里的数据摊平到低维空间（属于非线性降维），再计算点和点之间的欧氏距离，结合后续的监督学习。

LLE 局部线性嵌入 Locally Linear Embedding

原来的空间里面的点之间的关系用weight来表示，假设某一个点可以通过它的邻居的线性组合而成，因此我们需要让线性组合后的结果和原点的距离越近越好，也就是最小化所有的点的距离之和。总结：已知高维空间中的数据，求出数据之间的关系weight。

假设从高维空间到低维空间，描述空间里点之间关系的weight是不变的，因此可以用上面求出来的weight用同样的方式定义一个相似的函数。总结：已知的是数据间的关系weight，求的是低维空间中的数据。

LE 拉普拉斯特征映射 Laplacian Eigenmap

在semi-supervised learning中提出过graph-based approach以及定量描述smoothness相类似，最重要的区别在于有带label的数据项去约束smoothness的表达式。

我们希望close in high density region中的数据投射到低维空间之后数据还是很相近，但是要对投射后的结果加一点constraint，如果一开始的维度是M，那么找出来的那些在低维空间的点做span之后还会恢复成原来数据的M维度（可逆？）。

T-SNE

T分布随机领域 T-distributed stochastic neighbour embedding

why

以上都假设相近的点非线性降维之后都相近，但是却没有说不相近的点非线性降维之后都不相近（有可能不相近的点线性降维之后反而相近了）。

之前都是针对某一个数据locally的相近，如果从整体上看呢？我们要求投影前后的数据的分布distribution相近。

how

如何计算？

分别计算出所有投影前数据x之间的similarity（已知），并写出投影后数据z之间的similarity（未知），让这两个值之间的KL distance越小越好，从而可以求出未知的投影后的数据z。

如何定义和选择similarity？

分投影前数据的similarity和投影后数据的similarity考虑。

投影前数据的similarity用负的欧氏距离去exponent，因为距离一大，similarity就会非常小，确保了只有非常相近的点才有值。

投影后数据的similarity有两种方式。可以选择和投影前数据相同的衡量方式，这样总的方法就是SNE；但更好的是选择T-dirtribution中的一种用欧氏距离加上一，整体取个倒数作为similarity，这样总的方法就是T-SNE。

自编码器 auto encoder

想找一个编码器，input是一个比较复杂的东西，encoder就是一个neuron network，它的output就是code，维度远比输入要小实现了类似压缩的效果。

结构如下：input layer — layer1 — layer2 — … bottle… — layer2’ — layer1’ — output layer

input layer到bottle是属于encoder，bottle到output layer属于decoder，bottle的结果就是code。也就是dimension reduction的过程和reconstruct的过程。

TIPS on auto-encoder

Add Noise

de-noising auto-encoder，input加上noise之后再去encode，output要和加noise之前的原来的input越近越好。Neuron Network不仅学到了encode这件事，还学到了过滤噪音。

Pre-training

一般用于参数的initialization，pre-training就能让你找到一组好的初始化参数。

注意一般做auto-encoder的时候，希望coder的dimension要比input dimension小，如果coder的dimensionbiinput dimension大的话，需要加一个很强的regularization，避免auto-encoder直接把input并起来再输出（也就是learn不起来）。每一个步骤得到的weight都fix住，然后再输出结果之后再backpropagation微调fine-tune一下这些weight。

适合于大量unlabeled data存在，少量labeled data的情况。大量unlabeled data用于得出最初的weight，少量labeled data用于fine-tune。

应用

文本检索 Text Retrieval

把一篇文章压缩成一个code，利用降维将它表示成空间中的一个vector，现在有一个词汇用于查询，把查询的词汇也变成空间中的一个点，计算该查询次和每个document之间的内积，越大的内积代表相似程度最高。

如何把一个document表示成一个vector？

可以使用bag-of-word，vector的size就是所有lexical单词的个数，可以乘上weight代表每个单词的重要性。缺点在于缺失语义，词汇之间没有相关性。

可以使用auto-encoder使语义考虑进来。

类似图像搜索 Similar Image Search

如果单纯比较query image和database中image的pixel的相似度的话，结果会很不好。

需要用一个auto-encoder把image变革一个code，再在code上面去搜寻。

CNN auto-encoder

unpooling无池化，记录pooling的位置，把pooling后的值放在这个记录的位置上，其他都放0。或者也不用记录pooling位置，直接全部复制。

deconvolution反卷积，本质也是convolution，只不过weight相反。