unsupervised learning

同一系列的监督学习和神经网络相关笔记点击查看

无监督学习

监督学习和无监督学习的对比在监督学习开篇处已经介绍，此处不再赘述。

聚类算法Clustering

聚类就是对于输入特征x,算法会根据一些特征自动将其归为几类。与监督学习的数据集不同，这些数据集是没有y标签的。

K-means聚类算法

假设现在你需要算法寻找一个数据集中的两个集群，K-means算法做的第一件事是随机猜测这两个集群的中心在哪里，集群的中心称为集群质心，集群质心与输入特征x具有相同的维度。然后算法会遍历数据集中的每个数据，看一下他们与两个集群质心的差距，离哪个质心更近，就讲该数据归为哪一类。下图中❌和蓝叉就是算法最开始随机猜的两个值。

然后算法会计算红色集群的平均值，然后将最初预测的红色质心移动到红色集群的平均值处。同样的方式处理蓝色质心。
然后在新的质心基础上，算法会重复第一步，遍历数据集中的每个节点，再次计算他们对于质心的位置，如果发现原来被划分为红色集群的数据现在离蓝色更近，那么将该数据划分到蓝色集群。

然后再次计算新的集群的平均值，然后移动质心。重复执行这两个步骤，最后会导致质心的位置不再有变化，此时K-means算法就收敛了。

实现
计算数据和质心的靠近程度其实就是计算两者的距离$||x^i - \mu _k||$，也称为L2范数。在计算一个数据$x_i$与每一个质心$\mu_k$的距离以后，选择使距离最小的k,将其设置为$c^i$的值，$c^i$记录了一个索引，该索引记录了当前数据与哪个质心离得最近。当计算距离的时候，其实计算其平方会方便一些，而且效果是一样的。然后计算不同集群平均值即可得到不同集群新的质心。

有一个极端的情况：在分配集群的时候，没有任何一个数据属于一个质心，此时可以删掉这个质心，这也就会减少一个集群。如果不希望集群的数量减少，那么可以试一下重新随机一个质心位置，看看能不能将数据分配给他。
对于没有明显被划分为不同集群的数据集，K-means算法也可以较好的工作。比如衣服大小与人身高体重的关系，往往是一组连续的没有明显分组的数据，在这个数据集上使用K-means算法，依旧会得到比如k=3的3个集群，这三个集群的质心可以作为小、中、大号的代表。

代价函数
K-means算法的损失函数（失真函数distortion funciton）定义如下，他其实就是在找合适的质点，使得所有数据与其质点距离平方和的平均值最小。

以之前的例子为例，此时的状态，该模型的代价就是每一个蓝色的数据与蓝色叉距离的平方与每一个红色数据与红叉的距离的平方的和的平均值。

可以看到，该代价函数是$C^i$和$\mu_k$的函数，每个$C^i$与$x^i$是一一对应的，因为它代表了$x^i$是属于哪个质心的；而$\mu_k$本身就是质心的位置，所以这个代价函数会不断调整数据属于哪个集群以及不同质点的位置。

进一步来看一下K-means算法的每一步：
第一步是在将数据分配给不同的质心，此时质心是保持不动的。观察代价函数，若想让代价函数变小，很明显应该减少二者之间的距离，而K-means算法也正是这么做的，他将数据分配给了离自己近的质心。
第二步是数据已经分配好了，调整质心的位置。K-means算法做的是将新的质心位置取在集群的平均值的位置，事实上，这种做法会使所有样本的$||x^i-\mu_c^i||$和的平均值最小，也就是减少了代价函数。
也就是说K-means算法每一步都在降低他的代价函数，所以万一出现了代价函数升高的情况，意味着你的程序有Bug了。

质心初值的随机选择
之前说过K-means算法的第一步是随机选择一个质心，常见的做法是如果你需要k个质心，那么可以从数据集中随机选择k个数据作为初始的质心。
对于质心不同的初值，K-means算法在收敛后可能得到不同的聚类，如下图所示不同的初值得到了3个聚类。

因此为了是算法得到一个不错的效果，通常需要多次选择随机的初值，然后分别计算这些模型的代价函数，然后选择代价函数最低的模型。

质心（聚类）数量k的选择
有一个选择k的方法是叫肘算法（Elbow method），不得不说名字太难听了，还不如以发明者的名字命名。该方法将代价函数J()作为K的函数，观察J()的变化。如果发现了一点处函数的变化幅度发生突变，那么就选择该点处的K值。如下图中，K=3之前J()都在快速下降，但是k=3之后J()下降速度明显变缓，那么此时就可以选择K=3.但是J()往往也会想右图那样，找不到这样的K值。此时也不能找使J()最小的K值，因为随着K的增大，J()总是在减小。所以这个方法感觉不太行。

另外一种方法是权衡一下不同k值的效果，看看哪个更符合当前需求。比如在衣服尺码的数据集中，可以将k取为3，这样会得到三个聚类，这三个聚类可以分别代表小号，中号和大号。当然也可以让k=5，这样就得到了5个聚类，那么就可以分别代表超小、小、中、大、超大号。将衣服分为更多的类别，会增加制作成本，但是衣服会更贴合消费者的体型。所以在贴合消费者体型和制作成本之间，要做出一个权衡，以选择合适的k。

异常检测Anomaly detection

异常检测就是根据已有的数据集，判断新的数据与已有数据的相似性，以此来检测新的数据是否有异常。

异常检测最常见的方法是密度估计（density estimation）。该算法首先会建立一个关于特征x的概率模型$p(x)$，该模型的作用是检测当前特征的不同取值的概率。如下图最小的椭圆中的取值概率最高，向外慢慢降低。然后用该模型预测新数据，得到新数据的概率$P(x_{test})$,如果得到的概率小于某个阈值，那么就认为该数据有异常。

异常检测的应用很广泛，比如制造业中像检测引擎、欺诈检测、黑客攻击等。

高斯正态分布
为了应用异常检测，需要了解高斯正态分布。首先了解如何利用高斯分布实现单特征的异常检测。
高斯分布中，$\mu$是期望，也就是这组数据的平均数；$\sigma$是标准差，$\sigma^2$是方差，描述了这组数据的分散程度。

高斯曲线的方程为$p(x)=\frac{1}{\sqrt {2\pi} \sigma}e^{\frac{-(x-\mu)^2}{2 \sigma^2}}$,其曲线与x轴围成的面积恒为1，因此对于不同的$\mu、\sigma$该图像有如下变化：

根据数据集可以计算出$\mu、\sigma$，然后就得到了相应的高斯分布曲线。在此基础上，对于一个新的输入x，可以计算他的p(x),如果概率较高，那就认为这个数据没什么异常；相反如果这个值较低，那么就认为这个数据可能出现了异常。这了的数据只能是单特征，即x是个数而不是向量。

数据集x为向量时，可以依靠每个特征的p(x)来计算总的概率：$p(\vec{x}) = p(x_1;\mu_1,\sigma_1^2)p(x_2;\mu_2,\sigma_2^2)···p(x_n;\mu_n,\sigma_n^2) = \prod_{j=1}^{n}p(x_j;\mu_j,\sigma_j^2)$

多特征的异常检测检测算法，n不是数据集的数量而是可能导致异常的特征：

异常检测系统的评估

实数评估可以用于评估异常检测系统。通过实数评估，可以方便的选择特征x或者阈值$\varepsilon$之类的参数。
在无监督学习中，数据集是没有标签的，但是我们可以假设数据集有标签。如飞机发动机的数据集中，可以假设正常的发动机对应于y=0,异常的发动机对应于y=1.通常来讲异常发动机的数量是远小于正常发动机的数量的对吧。然后将数据集划分为三个部分，一部分用于训练模型，一部分用于调整参数，一部分用于评估模型。其中用来训练模型的数据集选用正常的发动机的数据，虽说是用正常的发动机训练，但实际上数据集中若参杂了一些异常的发动机也没关系。训练好模型以后，划分出一个交叉验证集和一个测试集，通过交叉验证集的结果来对模型进行微调，最后通过测试集来评估该模型的表现。这其实和之前的评估神经网络步骤很类似。

由于在异常检测的应用中，异常的例子往往很少，所以有时也可以不用单独划分出一个测试集。当然这样对于该模型的泛化评估就会差一些。

其实异常检测的数据集，正常的和异常的数量差别很大，如果给他们加上标签，那么这些数据集就是深度学习中，数据集偏斜很大的情况，在这种情况下，可以通过精确率、召回率、F1score这些参数来评估该模型。

异常检测 VS 监督学习

上边提到了给无监督学习的数据集假设标签，那其实就变成了监督学习，那二者的区别有什么呢？当正面的数据集很少，负面数据集很多的时候，异常检测会比较合适；当正面和负面数据都很多的时候，监督学习会比较合适。
当正面数据很少的时候，虽然二者都可以使用，但是二者看待数据集的方式截然不同。对于异常检测，负面数据是正常的情况，也是多数情况。那对于一个新的数据是否正常的判断的依据是他和负面数据的不同的程度，他是找不同，他不指望通过几个异常类型就能囊括所有的异常。比如诈骗，类型可以说层出不穷，诈骗er们天天在研究新的诈骗类型，如果指望查看信息诈骗的特征与以往就诈骗特征的相似程度，那诈骗er们就没饭吃了，他们在时时刻刻创新啊！而对于监督学习，他做的是通过大量的相应标签的数据，将它归为正面数据。对于新的数据，他看的是新的数据与以往已有标签的数据的相同的程度，他是找相同，像垃圾邮件，手段就那么些，改改数字，发发钓鱼网站，所以找相同更容易奏效。

特征选择

异常检测中，提供的特征需要是满足高斯分布的。在使用特征之前，可以绘制一下不同特征的曲线，如果不满足高斯分布，那么可以将特征做一些变形使他满足高斯分布。然后用变形过后的特征训练模型，交叉验证和测试。

有时，异常的数据经过p(x)后表现的和正常的数据差不多大，此时该模型对于异常的判断就不太理想，此时可以分析一下异常的数据，看看能否通过添加新的特征，该特征对于异常的数据和对于正常的数据有比较大的差异，这样就可以使该模型得到更准确的结果。

比如检测数据中心的电脑是否有异常情况，通常会用内存使用率、每秒访问磁盘次数、CPU负载、网络流量等指标来检测一个计算机是否异常。在处理不同业务时，对不同部件的使用情况也许会出现多种合理的不同情况，比如CPU负载高或低都正常，网络流量高或低也都正常，但是若在你的业务下，CPU高负载而网络流量低负载或者CPU低负载而网络流量高负载的情况不太会出现，那么此时可以新建一个特征为CPU负载和网络流量的比值，这个新特征既不会影响正常的数据，又能检测出异常数据。

推荐系统

推荐系统就是我想的那样，只是需要了解下图中的几个术语，其中问号表示该用户没有对该电影打分：

使用基本线性回归

假设我们已经有了电影的特征，我们可以使用如下方式来预测用户对没看过的电影的打分，其中n表示特征的数量，w和b的上标表示是第几个用户的参数。这看起来很像线性回归：

代价函数和线性回归模型也很类似，其中的正则化项，可以将分母的m去掉，m代表了用户评过分的电影的数量，是个常数，去掉它不影响参数w的取值：

上述是在训练单个用户的参数，可以将代价函数稍作修改，将所有用户的参数一起训练：

协同过滤算法collaborative filter

如果我们事先知道电影的特征x，则可以直接使用线性回归模型。如果我们事先不知道电影的特征，就无法使用线性回归。对于这种情况，假设我们现在已经有了每个用户的线性回归模型，即不同用户的w和b已知，我们又同时拥有不同用户对同一部电影的打分，而同一部电影的两个特征必然是一样的，因此我们可以根据不同用户的参数以及他们的打分情况来推测一下这部电影的不同特征的值：

具体的实现其实就是将代价函数作为特征x的函数，同样的可以一个个训练x，也可以一次性训练所有电影的特征x：

到此为止，我们分别在已知特征x的情况下训练了参数w和b，和已知参数w和b的情况下训练了电影特征x.协同过滤算法就是将二者结合起来，这样就得到了关于w、b、x的代价函数。注意到对于参数w的求和和对于特征x的求和虽然看起来有差别，但是实际上计算的项数都是一样的，他们的数量都是所有被用户打过分的电影的数量，只是解释起来的方式不太相同而已。

同样用梯度下降算法确定参数：

$$\begin{align*} &\text{repeat until convergence:} \; \lbrace \\ & \; \; \;w_i^{(j)} = w_i^{(j)} - \alpha \frac{\partial J(w,b,x)}{\partial w_j} \; & \\ & \; \; \; \; \;b^{(j)} = b^{(j)} - \alpha \frac{\partial J(w,b,x)}{\partial b^{(j)}} \\ & \; \; \; \; \;x_k^{(i)} = x_k^{(i)} - \alpha \frac{\partial J(w,b,x)}{\partial x_k^{(i)}} \\ &\rbrace \end{align*}$$

二进制标签

相对于给电影打分，更多的推荐算法是二进制标签的，像喜欢或是不喜欢这样的。于是预测任务就从之前的预测分数变成了预测用户是否喜欢，进一步，这其实就是从线性回归变成了逻辑回归，代价函数也和逻辑回归的代价函数很类似：

均值归一化mean normalization

之前的例子中，所有用户都已经评价过了一个或几个电影，那么对于新注册的用户，他没有对任何电影进行评分，因此对他执行协同过滤算法的话，会导致他对所有的电影的评分都是0.也就是无法完成给新用户推荐电影，很明显实际上不应该这样。

均值归一化可以解决这个问题。现在将用户对不同电影的打分组成一个矩阵A，A的每一行代表了不同用户对同一电影的打分。向量$\mu$的每一项表示表示用户对一个电影打分的平均值。用矩阵A减去$\mu$得到矩阵B，然后用矩阵B来学习新的参数w、b、x。学到新模型后，为了使预测保持在合理的范围之内，如评分非负，最终的预测结果需要在模型的预测基础之上加上对应电影的平均分数$\mu$.比如预测新用户对于第一个电影的评分，学习到的参数w、b为0，于是模型的预测打分是0,然后加上$\mu_1=2.5$,于是得到了最终的结果是2.5.这个结果比之前的0看起来更有说服力一些，他其实反映了其他用户对该电影的平均打分情况。
观察矩阵B的每一行，发现他们的均值为0，也就是上述算法其实将矩阵A的每一行都均值化为0.当有新用户注册时，想预测该用户对不同电影的评分用这种方法是不错的。但是还有另外一种情况，就是上映了一个新的电影，没有或者几乎没有用户对他进行过评分，这个时候想要预估用户对该电影的评分，可以将矩阵A的每一列均值化为0.

tensorflow实现协同过滤

两图胜千言

寻找相关特征

下面的方法可以找到和目标比较接近的一些东西，其实和代价函数很类似，只不过目标y换了一下而已：

协同过滤算法的局限性，图片中的第二个方面side information没看明白，他的意思是获取这些信息比较难吗？

内容过滤算法content-based filtering

内容过滤算法是根据用户特征和电影特征来推荐影片。用户和影片的特征可能是不同维度的，像用户有10个特征二影片有15个特征这样，所以向量$x_u^{(j)}$和$x_m^{(i)}$的大小是可以不一样的。

在协同过滤算法中，使用$w^{(j)}·x^{(i)}+b^{(j)}$来预测用户对电影的评分。在内容过滤算法中，需要使用$v_u^{(j)}$和$v_m^{(i)}$，他们分别是通过$w^{(j)}$和$x^{(i)}$计算而来，代表了用户j和电影i的特征的向量。而$b^{(j)}$项可以舍弃，这不会有什么影响。然后两个v向量的点积用来估计用户j对电影i的评分。虽然v是由x计算而来，而x的维度可以不同，但是v的维度必须相同。

计算$v_u$and$v_m$
可以分别使用两个神经网络来计算$v_u$and$v_m$,然后用$v_u·v_m$来预测用户对电影的评分。或者若想要得到一个二元分类的结果，将$v_u·v_m$作为参数传递给g()即可。注意到用户网络和电影网络输入层中的神经元数量不同，这代表了用户和电影的特征可以不同，但是他们的输出层有相同的神经元数量，这代表了他们最后的u的维度是相同的，便可以进行点积运算。

也可以同时构建两个神经网络，然后为整个神经网络定义一个代价函数，这样可以一次性计算所有的参数。若要想找与电影i相似的电影k，只需要计算$||v_m^k - v_m^i ||^2$即可。

从大型目录中推荐

大型目录指的代推荐的东西有很多，比如当一个用户访问不同网站时，该网站可能会推荐电影，推荐广告，推荐商品，推荐歌曲等等。这些代被推荐的东西有很多，如电影网站中有上万个电影、购物网站有上百万个商品等，如果每个用户来到这个网站，该网站就用上边提到的神经网络计算一次，那这个做法不太好，响应慢成本还很高。
为了解决这个问题，可以使用**检索（Retrieval）和排序（Ranking）**这两个方法。检索要做的有两个事情：首先选择出一些合理的stuff作为候选项；然后将这些候选项进一步筛选，比如重复的项扔掉，买过的项也扔掉，得到一个列表。排序要做的就是将检索好的列表用模型进行排序，比如将检索好的电影根据模型最后的预测评分由高至低排序。由于排序的列表是经过检索的，因此不会像最开始那样把所有的stuff丢给模型计算，这就大大降低了运算量。想想给你推荐的电影或者商品，100个算不少了吧，相比该网站所有的stuff上百万个，极大的降低了运算量。而且，网站已有的stuff的对应$v_m$是可以提前计算的，所以当有用户访问网站时，只需要计算该用户对应的$v_u$即可，这又进一步的降低了运算量。

可以看出，检索其实就是做了一次广度的覆盖，而排序的目的是为了更精准的推送。那现在要思考的问题是，在第一步检索的过程中，筛选出多少stuff比较合适。容易想到，检索的stuff越多，那么推荐的效果就会越好，但是相应的速度也会降低。因此需要在性能和速度之间做出权衡。一个有效的方法是进行离线实验，看一下

Tensorflow实现内容过滤算法

见jupyterLab

Principal Component Analysis

将数据可视化
一个汽车又长和宽两个特征，但是汽车的宽度变化范围其实差别不大，而汽车的长度变化范围较大，此时为了见数据可视化，可以忽略变化幅度小的特征像这里的汽车宽度。

再比如若两个特征为汽车的长和高，大小不同的车的这两个参数会有较大的差异，就是说这两个特征的变化幅度都挺大的，无法直接忽略任何一个，此时可以创建一个新的特征来描述这两个特征。比如新建一个z轴表示车的尺寸，这里的z轴不是新建了一个维度，还是在二维空间内新建的，他和x、y在同一平面。车的尺寸越大，相应的长度和高度就越高，因此可以用z这一个特征来粗略的估计x和y.

下图中的数据有3个特征，我们可以在三维坐标系中描绘出这些数据。但是若将三个特征减少到两个特征，我们就可以在二位坐标系中描绘出这些数据，会更方便一些对吧。

如果要描述一个国家，那一个国家的特征可太多了，如GDP，人口数量，占地面积，男女比例等等。假设一个国家有50个特征，我们一定是无法将有50个特征的国家可视化的。PCA算法可以将这大量特征减少到2、3个，这样我们就可以在坐标系中描绘出不同国家了。如经过PCA算法后，将这50个特征减少到了2个，这两个特征大致相当于GDP和人均GDP，这样我们就可以将一个国家在坐标系中可视化。

PCA算法
在使用PCA算法之前，需要先将特征进行放缩，让他们的变化范围大致相同。然后将放缩过后的特征归一化为0均值，就是把每个特征减去平均值。

接下来选择一个新的坐标轴来代替原来的两个坐标轴，比如这里选择坐标轴z，其实和之前的x1坐标轴一样。选择z作为新的坐标轴后，将原来的五个数据映射到z轴上，我们可以知道他们的变化幅度很大，这也是一种比较有效的信息。

如果将z轴选成这样，将数据映射到z轴后，他们的变化幅度不如上一个z轴那样明显，所以这个新的坐标轴选的就不如上一个。

如果将z轴选为下面这样，那此时数据在z轴上的映射会得到最大的变化范围，此时的z轴就被称为主成分：当将数据映射到其上时，会得到最大的方差。

有了主成分之后，想要将二维的数据映射到主成分上，要做的就是将原数据向量和与主成分方向一致的单位向量做点积，就会得到其在主成分上的投影。想这里原数据向量是(2,3),假设找到的主成分是与x1夹角pi/4,从原点出发的指向第一象限的射线，那这个单位向量的坐标大概是(0.71,0.71),然后二者做内积，于是便计算出了x在主成分上的投影是3.55.

找到了主成分之后，如果还想要更多的主成分，那么只需要让这些主成分互相垂直(perpendicular).如要找第二个主成分，只需要和第一个主成分垂直即可，此时还在二维平面。若还想再找一个主成分，就需要与前两个主成分都垂直，也就延展到了三维空间。

只有两个特征的时候，PCA看起来和线性回归很类似，但是大多数时候数据集的特征很多，这个时候PCA和线性回归看起来就有很大不同了。实际上这两者本身就是两个事情，线性回归是监督学习中的事情，他有y标签，他想找的是一条和数据集拟合程度好的曲线，目的是尽量靠近y.而PCA没有y标签，他对待所有的特征都是平等的，他想找的是一条能尽量保留特征差异的曲线，这样将数据可视化的时候能看得更清晰一些。

特别的，若数据集是这样，即使仅有两个特征也能看出来二者的不同。

反过来，若给出映射后的数据，可以通过PCA重建来近似还原出原来的数据。如给定的z=3.55,与单位向量相乘后得到了(2.52,2.52),这和原始数据(2,3)相差不大。

PCA实现
可以使用scikit-learn包来实现PCA算法。使用前若数据不同特征的变化范围太大了，需要预处理，将不同特征放缩到一个合适的范围，这有助于找到合适的主成分。然后就可以使用sl包来完成其他事情。其中的fit函数会自动完成特征的归一化为均值0.

参数n_components=1表示只想要1个主成分；explained_variance_ratio_输出0.992表示经过PCA后的主成分，也就是新的坐标轴，保留了原始数据99.2%的变化率，看起来很不错。

若将二维的数据映射到二维的数据，就是说选两个主成分，那会出现这样的结果。其中explained_variance_ratio_有两个输出，0.992和0.008,分别代表了在不同的主成分上保留的原始数据的差距的比例，二者之和为1,就是说能完全解释原数据。

关于PCA的一些早期应用，现在的主要应用还是将数据可视化：

强化学习

假设现在有一个无人机，将无人机的位置，方向和速度等信息称为状态。强化学习做的就是对于给定的状态s，找到一个函数将其映射为a，a是怎么操作摇杆让他保持想要的状态，像让它待在固定位置不同这样。虽然我们也可以使用监督学习来做这个事情，这不但需要对于无人机状态x的大量观测，同时需要比较专业的人来说明对于一个x应该怎么操作摇杆，也就是y.但这是很难做到的，因为这种操作无人机的顺序和力度很难精确说明，比如向左倾斜多一点还是少一点，这个一点儿怎么衡量；又或者是给无人机多少动力，这些都决定了x如何映射到y，这无疑是很困难的。正因如此，很多对于机器人的控制的应用中，监督学习的效果并不理想，而要使用强化学习。
强化学习之所以强大的一个原因是你只需要说明做什么，而不需要说明怎么做。这就需要奖励函数，如果飞机飞得好，那可以将某个值+1，飞得不好则—1，如果飞的坠毁了，-10000这样。

火星探测器模拟
一个简化的火星探测的例子：探测器的初始状态为4,现在状态1和状态6都是值得探测的地方，但是状态1更有价值一些，因此可以将状态1的奖励设置的更高一些。探测器每次向左或向右移动，每次移动到新的状态都会得到奖励。如过探测器一直向左走，走到3的时候，得到0奖励，走到2的时候，得到0奖励，走到1的时候，得到100奖励；同样它也可以一直往右走；又或者左走走右走走。假设他走到1或6的时候，他就不会继续做其他事情，那状态1和状态6就是终端态。当他每一次行动的时候，都有4个参数：(状态，动作，奖励，下一个状态)，这几个参数是强化学的的关键信息。

回报

通过之前的例子可以知道，不同的动作序列可能得到的奖励是不同的，通过强化学习的回报可以捕获不同序列的奖励。回报捕捉到的通常是能快速得到的奖励。像你身边现在就有10块钱，但是在山的那边有20块钱，回报会捕捉身边的这10块钱。计算回报公示如下图所示，第一项是初始状态的奖励，然后依次相加直到终端态。其中$\gamma$是折扣因子，他是小于1的，通常取很接近1 的值如0.99等。正是折扣因子的存在导致了回报会更倾向于离得近的奖励。

假设现在一直向左走，从不同状态出发得到的回报用红色的字在上边注明了。需要注意的是如果从状态6开始，那么他的起始状态就是终端态，因此计算回报时只有一项，就是该终端态的奖励，也就是40.类似的，一直向右走的话，各状态作为起点的回报如图所示。当然如果在不同的初始状态选择不同的动作，那就可以得到第三个表格中的回报。

决策学习算法的策略
决策学习的目标是构建一个可以将状态s映射为行动a的Policy函数$\pi(s)$,该函数会告诉我们为了得到最大的回报，每一步应该怎么做。如对于之前的例子中的最后一行，policy函数作为不同状态的函数会得到相应的行动。

看一下强化学习中的不同参数在不同应用中可以对应什么。

这种强化学习应用程序的形式可以称为马尔科夫决策过程Markov Decision Precess(MDP).从之前的例子中可以得知，MDP说明了未来只取决于当前的状态，而不取决于是怎么到当前状态的。MDP也可以用下面这种图来解释：Agent是我们要操作的东西，经过Policy函数后得到了动作a，做了a之后会发生一些变化，比如我们的位置。基于这些变化，我们可以看到当前的状态以及奖励。

State-action value 函数定义

状态动作做价值函数也可以叫Q函数，它以当前的状态s和当前要采取的行动a作为参数。当在状态s做了a动作之后，到达了一个新的状态，在这个新的状态下有最大的回报的路径即最优策略。Q函数返回的是从最初的状态s到新的状态再走最优策略的总回报。如对于状态2，若首先向右走到达状态3，根据之前计算过的最优策略，从状态3开始的最优解是往左走，于是便一路向左，这条路径的回报是12.5;若往左走，则直接到达了终端状态，回报是50.这样就可以计算出所有状态的Q值。

这里感觉比较奇怪，因为策略函数已经计算出了最大回报的路径是什么，为什么还要这个函数。比如在状态2的时候，明明知道了最优解是往左走，为什么还要计算一下往右一步，然后再走最优解。

对比Q函数和策略函数，发现每个状态的策略函数的回报就是Q函数取不同动作回报的最大值，这也给策略函数的计算提供了一种方法。Q函数也叫Q*或者最优Q函数或状态动作价值函数。

贝尔曼方程

贝尔曼方程可以用来得到Q函数。刚查了一下，贝尔曼方程又较动态规划方程，OK,fine.挺希望有一天术语能统一一点，机器学习好像挺多概念就是数学概念换个叫法。

在看几个，注意的是若起始状态s是终端态，那么他不会采取行动，于是Q函数就只剩下第一项了。

回报可以分为两部分，一部分是马上能得到的回报，另一部分就是走到下一个状态后能得到的最佳回报，这也是贝尔曼方程要说明的主要事情。

随机环境random(stochastic) environment

实际工作中，机器人可能不会完全按照我们发出的指令执行。比如我们让他往右，但是他轮胎打滑了没有往右等，这就是随机环境。比如火星探测器的例子中，若初始状态在4号，现在你让他往左走，但是由于各种原因，比如风太大了，轮胎打滑了等等，最终导致了他有90%的概率往左走到3但是还有10%的概率往右走到5。考虑到这些随机的情况，就引出了期望回报。期望回报就是将一个设序列重复执行多次以计算他得到回报的平均值。所以，强化学习的目标到现在就变成了找到一个策略函数Policy()以得到最大的期望回报。同样，贝尔曼方程也要改进一下，加上期望。

连续状态空间
火星他测器的例子中，探测器只在一些离散的位置，但实际应用中状态往往是连续的，并且一个物体的状态往往是多维的，比如x坐标，y坐标，x方向速度，y方向速度等。

登月器

强化学习的主要任务是训练一个神经网络来逼近Q函数。登月器中，用于训练神经网络的输入可以由两部分组成，一个是登月器的状态，另一个是可以采取的行动，二者组合成一个向量作为输入。其中动作a有4个可能，什么都不做、向左点火、向右点火和向下点火来控制登月器的位置，以确保他能落在目标位置。将特征a经过one-hot编码得到4个二进制编码，在拼接上状态作为整体的输入向量。如当登月器在一个状态后，经过神经网络的计算，发现Q(s,main)最高，mian表示向下点火，那么登月器便会向下点火。

那现在问题就是怎么样训练这个神经网络。我们可以通过贝尔曼方程得到一些训练集x和y，然后用监督学习来训练神经网络。为了得到训练集，我们可以让登月器随即采取行动，这样可以得到很多不同的元组(s,a,R(s),s’).根据s和a就可以得到输入x,根据R(s)和s’就可以得到Q(s,a)也就是y,于是就有了第一个数据集。其中贝尔曼方程的第一项就是R(s),而第二项需要的参数s’需要利用下一个元组的信息。在最初的时候，我们并不知道Q函数是什么，但是可以在最初的时候假设一个Q函数。

完整的训练过程，这个算法叫做DQ(Deep Q-Network)N算法：

算法改进

改进神经网络架构
之前的架构中，将动作a作为参数传给神经网络，于是对于同一个位置，神经网路一次只能计算对于该位置的一个动作。现在对输输入和输出做出改变，动作不作为输入，而在输出层中设置4个神经元，分别代表了不同动作的Q值，于是这样就可以一次计算出同一状态的4个不同动作的Q值。

$\varepsilon$贪婪策略
当神经网络正在学习的时候，以前的方式中，他在每个状态总是采取能获得最到回报的动作。但是由于最初的Q函数是随机的，他有可能随机到一种情况，导致某个动作永远会使Q函数很低。比如Q(s,main)总是比较低，main表示向下开火，于是最终学到的Q函数就永远不会向下开火。为了避免这种情况，我们可以不必每次都选择能使回报最大的动作，当然应该尽量选择这个，只不过应该给他个权重像0.95，剩下的0.05权重让模型选择一个随机的动作，这个选择随机动作的做法被称为“探索”。这个策略就是$\varepsilon$-greedy policy，其中$\varepsilon$=0.05.
$\varepsilon$-greedy policy常见的做法是以一个比较高的$\varepsilon$开始，逐步降低其值。比如登月器中，甚至可以将$\varepsilon$初始化为1，然后逐渐减小到0.01.

小批量和软更新
小批量不但能提高强化学习的性能，也能加速监督学习，像提高一些神经网络的训练或者线性回归模型的训练速度。
在监督学习中，我们使用梯度下降算法来训练参数的时候，每次梯度下降都会遍历一边所有数据集，当数据集很大的时候，这会导致梯度下降的很慢。小批量做的是取大数据集的一个小子集，每次用这些小子集更新参数而不是遍历整个数据集，这样速度就会快不少。其中每次迭代使用的子集可以是不同的，可以将整个数据集划分为n个不同的子集，或者有一些交集的子集，然后用这些子集分别进行每一次迭代。

普通的梯度下降中，每次迭代都会使代价函数减少。而小批量梯度下降时，由于每次使用的数据集只是一个局部的缘故，他可能在单次下降过程中效果不太好甚至有时会增加代价函数，但是该算法的总体趋势仍然是向着全局最优的地方。所以在有大量数据集的时候，往往更多地使用小批量梯度下降或者Adam算法而不是最普通的梯度下降，因为他们的速度更快且最终的效果也不错。同样的在登月器的例子中，让登月器先随机获取10000个数据样本以后，可以不全部使用这些样本，而是一次使用1000个样本这样。

在登月器的算法中，最后我们将Q设置为Qnew,这里有可能发生的一个情况是新训练的Qnew可能性能还不如最开始的Q函数，软更新可以防止这样的事情发生。对于$Set Q = Q_{new}$,其实就是将参数$W_{new}、B_{new}$分别赋给了旧的$W、B$.其实我们可以使用$W = 0.01W_{new} + 0.99W、B = 0.01B_{new} + 0.99B$这样的更新方式。0.01和0.99是超参数，二者的和为1，他们控制了参数像新的参数靠拢的程度。如当只给新的参数0.01权重而给旧的参数0.99权重的时候，说明参数只是做了小幅度的更新，他还是更靠近旧的参数。这种做法可以让强化学习算法收敛的更可靠。

一些问题

关于K-means算法的第二步，选择样本的平均值作为新的质点的位置，那么此时每个样本与质点的差的平方的和平均值最小的数学证明。（当质点这么取值的时候实际上这个式子就变成方差了对吧）

协同过滤算法使新用户的评分是0

使用协同过滤算法训练模型：

$$\begin{matrix} \textbf{min}\\ w^{(1)},...,w^{(n_u)}\\ b^{(1)},...,b^{(n_u)}\\ x^{(1)},...,x^{(n_m)}\\ \end{matrix} \qquad \frac{1}{2} \sum_{(i,j):r(j,j)=1}(w^{(j)}·x^{(i)}+b^{(j)}-y^{(i,j)})^2 + \frac{\lambda}{2} \sum_{j=1}^{n_u}\sum_{k=1}^{n}(w_k^{(j)})^2 + \frac{\lambda}{2} \sum_{i=1}^{n_m}\sum_{k=1}^{n}(x_k^{(i)})^2$$

我们的目的是使代价函数尽可能小。对于新用户，他为对任何电影做出评价，因此代价函数的第一项是0,在此基础上，若想使整体式子变小，明显w的取值是0.类似的，若还对b做了正则化，则b也为0,所以新用户在该模型上对任何影片的预测分数都为0,不便于推荐。
刚写上边这几行的时候又想到在监督学习中，这几项也都是平放项，要使该式子最小岂不是也应该让w为0吗？稍微一想就清楚了，在一般的监督学习中，w的值会影响到无正则化的代价函数，也就是式子的第一项，因此两者合作才能得到最小的代价函数。而协同过滤算法中的新用户无第一项，决定整个式子的只有正则化项，因此w才为0.

协同过滤算法不适应密集层

videop122 min10左右，Andrew说协同过滤算法不能适应密集层那一段，没明白。他说了需要自己实现代价函数，之前不也是自己实现代价函数吗。可能是我记错了，以后看一下tensorflow密集层的代价函数相关部分是怎么做的，和协同过滤算法有什么区别。

协同过滤算法和内容过滤算法的区别

on Andrew’s slide:
Collaborative filtering:
Recommend items to you based on rating of users w·o gave similar rating as you.
Content-based filtering:
Recommeng items to you based on features of users and item to find good match.

查找一些资料，发现协同过滤算法分为用户协同过滤和物品协同过滤。Andrew说的应该是用户协同过滤。但是实现方式中是一起训练w、b和x,没看出来找相似用户这个过程。

Q函数

Q函数的作用没太清楚，他能计算出策略函数，但他采取行动走的需要时最优解，这最优解如果不是通过策略函数找到的，那是怎么找到的。