举个例子，假如筐里有100个苹果，让我每次闭眼拿1个，挑出最大的。于是我随机拿1个，再随机拿1个跟它比，留下大的，再随机拿1个……我每拿一次，留下的苹果都至少不比上次的小。拿的次数越多，挑出的苹果就越大，但我除非拿100次，否则无法肯定挑出了最大的。这个挑苹果的算法，就属于蒙特卡罗算法——尽量找好的，但不保证是最好的。

而拉斯维加斯算法，则是另一种情况。假如有一把锁，给我100把钥匙，只有1把是对的。于是我每次随机拿1把钥匙去试，打不开就再换1把。我试的次数越多，打开（最优解）的机会就越大，但在打开之前，那些错的钥匙都是没有用的。这个试钥匙的算法，就是拉斯维加斯的——尽量找最好的，但不保证能找到。

MCMC最优要拿完。
拉斯维加斯则不用拿完

这两个词本身是两座著名赌城，因为赌博中体现了许多随机算法，所以借过来命名。

如果问题要求在有限采样内，必须给出一个解，但不要求是最优解，那就要用蒙特卡罗算法。
反之，如果问题要求必须给出最优解，但对采样没有限制，那就要用拉斯维加斯算法。

例子

下棋

对于机器围棋程序而言，因为每一步棋的运算时间、堆栈空间都是有限的，而且不要求最优解，所以ZEN涉及的随机算法，肯定是蒙特卡罗式的。

机器下棋的算法本质都是搜索树，围棋难在它的树宽可以达到好几百（国际象棋只有几十）。在有限时间内要遍历这么宽的树，就只能牺牲深度（俗称“往后看几步”），但围棋又是依赖远见的游戏，甚至不仅是看“几步”的问题。所以，要想保证搜索深度，就只能放弃遍历，改为随机采样——这就是为什么在没有MCTS（蒙特卡罗搜树）类的方法之前，机器围棋的水平几乎是笑话。而采用了MCTS方法后，搜索深度就大大增加了。

求无理数 - 投针求pi

针投的越多结果越准，但是找不好最优解，只能找到近似。

求无理数 - 求解积分

求解交通状况堵塞模型

规模零件集成后的不合格率

https://www.zhihu.com/question/20254139/answer/33572009

蒙特卡洛树搜索

蒙特卡洛树搜索（英语：Monte Carlo tree search；简称：MCTS）是一种用于某些决策过程的启发式搜索算法，最引人注目的是在游戏中的使用。一个主要例子是电脑围棋程序[1]，它也用于其他棋盘游戏、即时电子游戏以及不确定性游戏。

不穷举所有组合，找到最优或次优位置

围棋棋面总共有$19 * 19 = 361$
个落子位置。假如电脑有足够的计算能力，理论上来说，我们可以穷举黑白双方所有可能的落子位置，找到最优落子策略。

但是，如果穷举黑白双方所有可能的落子位置，各种组合的总数，大约是 $250^{150}$数量级。这个数太大了，以至于用当今世界最强大云计算系统，算几十年也算不完。

需要说明的是，蒙特卡罗树搜索并不是只有一种算法，而是一类算法。其中最流行的算法之一就是UCT（upper confidence bounds applied to trees）。

蒙特卡洛树搜索（英语：Monte Carlo tree search；简称：MCTS）是一种用于某些决策过程的启发式搜索算法，最引人注目的是在游戏中的使用。一个主要例子是电脑围棋程序[1]，它也用于其他棋盘游戏、即时电子游戏以及不确定性游戏。

下棋其实就是一个马尔科夫决策过程（MDP），根据当前棋面状态，确定下一步动作。

在每个模拟游戏中，AlphaGo都有两个大脑指引它进行搜索：价值网络（value network）和政策网络（policy network）。“政策网络”观察棋盘布局企图找到较好的下法，“价值网络”则预测这样下的话对方棋手赢棋的可能。结合这两个建议，AlphaGo最终决定怎样落子才是胜算最大的。

维特比

为什么不用维特比算法，能把指数级搜索缩小到N^2级。而且是最优化解。

2018-06-20

Math►-运筹学-动态规划

P：算起来很快的问题
NP：算起来不一定快，但对于任何答案我们都可以快速的验证这个答案对不对
NP-hard：比所有的NP问题都难的问题
NP-complete：满足两点：

是NP hard的问题
是NP问题

参考

https://www.zhihu.com/question/27039635

2018-06-20

Math►-optimization

优化方法总结比较（SGD，Adagrad，Adadelta，Adam，Adamax，Nadam）

参考

2018-06-20

ML►ml 传统方法►降维

SVD、PCA、LDA、LSA、PLSA、LDA

PCA

PCA有两种通俗易懂的解释，1)是最大化投影后数据的方差(让数据更分散)；2)是最小化投影造成的损失。这两个思路最后都能推导出同样的结果。

其方法主要是通过对协方差矩阵进行特征分解[2]，以得出数据的主成分（即特征向量）与它们的权值（即特征值[3]）。PCA是最简单的以特征量分析多元统计分布的方法。其结果可以理解为对原数据中的方差做出解释：哪一个方向上的数据值对方差的影响最大？换而言之，PCA提供了一种降低数据维度的有效办法；如果分析者在原数据中除掉最小的特征值所对应的成分，那么所得的低维度数据必定是最优化的（也即，这样降低维度必定是失去讯息最少的方法）。主成分分析在分析复杂数据时尤为有用，比如人脸识别。

PCA和SVD的关系？一个根据covariave。一个是特征值。有什么联系。

LDA不记得了。

图片来自 https://stats.stackexchange.com/questions/134282/relationship-between-svd-and-pca-how-to-use-svd-to-perform-pca

PCA与FA

因子分析(FA)与主成分分析(PCA)的区别
(1)主成分分析是将主要成分表示为原始观察变量的线性组合，而因子分析是将原始观察变量表示为新因子的线性组合，原始观察变量在两种情况下所处的位置不同。

PCA与SVD

简介

Matrix Factorization
SVD

u =

-0.825066 -0.047735 -0.563016
-0.443084 -0.563669 0.697104
-0.350631 0.824620 0.443914

s =

Diagonal Matrix

9.2654 0 0

0   3.2340        0

0        0   1.3016

v =

-0.636527 -0.770982 -0.020485
-0.476317 0.372083 0.796666
-0.606593 0.516857 -0.604073

U V有个特性，每行，每列的平方和都等于1.

Matrix Factorization
应该是，Diagonal Matrix中比较大的值，对应的U，V相应的行列，影响权值越大。
特征值分解必须针对方阵，即只有方阵才有特征值，这也是特征值分解的一个局限

Q是矩阵A的特征向量组成的矩阵，Q不唯一
一个矩阵其实就是一个线性变换，因为一个矩阵乘以一个向量后得到的向量，其实就相当于将这个向量进行了线性变换

奇异值分解
在很多情况下，前10%甚至1%的奇异值的和就占了全部的奇异值之和的99%以上了

一个很好的tutorial

fed

实质是降维
对矩阵X和V的理解，X是latent vector representations ，V是词典，也就是latent space的坐标系。当然也可以U作为表达，sigma*V作为词典

我的实验
要解决的问题：
对1000个样本进行降维，我们可以采用SVD分解。如果又来了一个新样本，如何获得这个样本的降维表示？
方法一：与原始样本组成1001的矩阵，然后整体矩阵进行SVD分解（计算复杂度较高）。因此我们提出一下问题

SVD分解是否对新增样本具有不变性，包括1.降维表达不变性；2.词典不变性？？？
对 100030的矩阵进行svd分解，并降维到100020。
100030=【100020】【2020】【2030】=【100020】【20*30】，这里第一项是降维表示，第二项是词典

新增一个样本，变为100130，对其SVD分解，U,S，V 与原始的USV几乎不变，只是增加了相应的行和列。这就寻找到了一个不变的量。
然后具体如何获得一个新样本的降维表示呢？
130=【120】【20*30】
Ax=Y，超定方程组，一般无解，只能求近似解
类似超定方程求解，以下程序的方法不一定很好。

---------------------------------------------------------------
clear,clc
a=rand(100,1);       %a作为训练集
[U,S,V]=svd(a);
a20=U*S(:,1:20)*(V(1:20,:))';    %降维到20维后的重建
error=sum(sum(abs(a-a20)));
aplus=[a;rand(1,30)];

%方法一：
[U1,S1,V1]=svd(aplus);     % 对所有样本进行SVD分解
P1=U1(101,:)*S1(:,1:20);    % 新样本降到20维后的表示

%方法二：利用求解超定方程组的方法
P2=inv(V'*V)*V'*aa'         %利用训练集得到的词典，求得的新样本表示
P3=inv(V1'*V1)*V1'*aa'      %利用所有样本降维后的词典，求得的新样本表示
-------------------------------------------------------------------
P1=P3。说明这个方法很好，也就是把超定方程组化为普通方程组。这个方法有点类似

疑问

对于稀疏矩阵，降维策略可以有哪些优化？

独一无二的数字多了，为什么不用素数？素数也是越来越难算，或者设计个其他数字。

如何保证数字主人的唯一性？数字被别人知道了，是不是比特币就被盗了？大家都知道这个数字怎么办？

什么是MCMC

例子

下棋

求无理数 - 投针求pi

求无理数 - 求解积分

求解交通状况 堵塞模型

规模零件集成后的不合格率

蒙特卡洛树搜索

维特比

参考

参考

PCA

PCA与FA

PCA与SVD

简介

fed

疑问

参考

求解交通状况堵塞模型