读书笔记2
8-7 最近实在是没法完成每天的读书笔记，加上上本书又到了充满细节没有直观的部分，完全读不下去。。从今天开始尽量重新建立工作的习惯，所以今天换了一本书：Geometric Modeling in Probability and Statistics。重点在于尽力专注而不是效率。看了第一章，先回顾了一下概率论，然后从微分几何的角度定义Fisher information和它的Levi–Civita connection (Christoffel symbols)。Fisher information的定义方法是 https://www.zhihu.com/equation?tex=g_%7Bij%7D%28%5Cxi%29+%3D+E_%7B%5Cxi%7D%5B%5Cpartial_%7B%5Cxi%5Ei%7D+%5Clog+p_%5Cxi%5Cpartial_%7B%5Cxi%5Ej%7D+%5Clog+p_%5Cxi%5D. 其实学到这个定义很多次了，每次都没感觉。这次可能从例子入手看看，比如exponential family https://www.zhihu.com/equation?tex=p%28x%3B%5Cxi%29+%3D+%5Cexp+%28C%28x%29+%2B+%5Cxi%5Ei+F_i%28x%29-%5Cpsi%28%5Cxi%29%29 的Fisher information是 https://www.zhihu.com/equation?tex=%5Cpartial_i%5Cpartial_j+%5Cpsi%28%5Cxi%29+%3D+Cov_%7B%5Cxi%7D%28F_i%2CF_j%29 ，所以和 https://www.zhihu.com/equation?tex=%5Cpsi 的Hessian有关系，让我想起了另一本书curvature和support函数的Hessian有关，不知道有没有什么联系。因为如果把这些Hessian看成change of variable的积分里乘的那一项的话，那么change of variable就是对应函数的gradient，其实应该是有点意义的，留个坑之后再填。另外是Christoffel symbols of first kind定义成 https://www.zhihu.com/equation?tex=%5CGamma_%7Bij%2Ck%7D+%3D+%5Cfrac%7B1%7D%7B2%7D%28%5Cpartial_i+g_%7Bjk%7D+%2B%5Cpartial_j+g_%7Bik%7D+-+%5Cpartial_k+g_%7Bij%7D%29 . Exponential family 的Christoffel symbols 是 https://www.zhihu.com/equation?tex=%5CGamma_%7Bij%2Ck%7D+%3D+%5Cfrac%7B1%7D%7B2%7D%5Cpartial_i%5Cpartial_j%5Cpartial_k+%5Cpsi%28%5Cxi%29 。在定义了一些其他的connection之后，最后Jeffrey’s Prior定义成 https://www.zhihu.com/equation?tex=%5Csqrt%7B%5Cdet+g_%7Bij%7D%28%5Cxi%29%7D normalize后的probability，这边 https://www.zhihu.com/equation?tex=%5Cdet+g_%7Bij%7D 对于exp family来说是log partition fn的Hessian的det，其实让我想起optimal transport的公式，不过distribution做change of variable都是需要这一项的，就是积分换元里乘的那一项，所以依然不知道有什么意义，可能与opt transport关系不大。。8-8 今天划过了entropy、KL、information energy、max ent几章，基本是复习。比较有趣的是， https://www.zhihu.com/equation?tex=%5Cpartial_i+%5Cpartial_j+D_%7BKL%7D%28p_%7B%5Cxi_0%7D%7C%7Cp_%5Cxi%29%7C_%7B%5Cxi%3D%5Cxi_0%7D+%3D+g_%7Bij%7D%28%5Cxi_0%29 ，这里 https://www.zhihu.com/equation?tex=g_%7Bij%7D 是Fisher information，所以Fisher metric可以看作是KL-div的2nd order approximation。另外，information energy介绍非常的厉害，和热力学相关之类，但是其实就是density的L2-norm平方，就是quadratic energy，不得不感叹quadratic到哪里都很有用。max ent的话，和exp family有关，这些关联包括一些KL的variational form，一度让我非常着迷，总觉得在那些计算下面有一些东西，每次深想想不到就觉得应该是错觉。过两天组里的人会给个报告关于这个，希望会有一些启发。最后就是读了differential geometry的简介章的一半，manifold、tangent space、Lie bracket。之前学这些东西，即使学的时候会，但是过一阵子又会一头雾水，我感觉问题在于DG的东西分为抽象和计算两类，运用不同的数学符号，抽象的符号就不知道实体是什么，计算的那块index又太过复杂，所以许久不用就完全忘记了。其实正确的理解方法应该是，抽象的那块从泛函的角度想，也就是定义在函数空间上的一些operator，线性加一些其他性质；而计算的那块就从线代的角度去想，也就是用coordinate的一些基来把抽象的东西简化成tensor来计算。直觉的话，就像空间曲面曲线就好。之前可能直觉想的太多，导致抽象和计算的符号都不太熟，这次稍微把这几项结合一下。
8-10 最近缓慢地试图重建对DG的抽象的感觉，稍微用泛函的理解过程类比了一下。重点是要弄清楚不同空间的层级关系，以及各个符号在哪个空间。具体看了tangent space(+Lie bracket), differential, 1-form 和tensor。在流形上定义的光滑函数空间算是最底层，往上一层是tangent space（定义在光滑函数上的线性满足chain rule的operator，类比dual space），再往上一层是cotangent space（类比dual of dual space）。最后tensor是定义在多个tangent space和cotangent space的cross product上的线性operator。比泛函麻烦的地方在于，这里不同层次的空间是可以搅合在一起的233. 因为虽然在流形单点上是这个结构，但是从全局上看，每个结构都算是流形上的函数，所以可以和real-valued函数进行运算。比如tangent space对于这样的（和函数的乘法）运算就不是线性的，但是tensor对这样的运算依然是线性的。这些其实在微积分这样的Euclidean空间上的函数非常的显然且常用，但是到了manifold上的函数就没有那么好想，可能还是没有习惯吧。
8-14 最近啃的非常艰难，因为迎来了微分几何的tedious的部分，各种定义和计算非常头大。于是跳了一堆之后，来到了第11、12章，contrast function相关，终于知道了一些为什么之前看很多东西都很眼熟的原因。。contrast function是KL divergence的一个推广，它可以（用二阶导数）定义一个Riemannian metric。有三个例子。一个是f的Bregman divergence做contrast function，定义的metric是 https://www.zhihu.com/equation?tex=g_%7Bij%7D%28x%29%3D%5Cpartial_i%5Cpartial_j+f%28x%29 ，如果f 取exponential family的log partition function，那么对应的metric就是exp family的Fisher metric。第二个是second fundamental form，也是由Gauss map的二阶导定义的（那么问题来了，这个和上面的Bregman div有关吗？），接着eigenvalue定义了curvature。另一个例子是满足某种条件的f给出的f-divergence做contrast function，给出的metric 就是Fisher metric。这就是为什么之前总觉得curvature、exp family、Fisher inf之间很像。也许有一些深层的东西，应该是Amari的研究领域，也许DG可以告一段落了2333
8-18 最近的生活非常兵荒马乱，但是就是在混乱的时候才需要用纪律性约束自己。最近根据老板的任务看了Paul Dupuis的两篇文章，Formulation and properties of a divergence used to compare probability measures without absolute continuity 和 (f,Gamma)-divergences: interpolation between f-divergences and integral probability metrics。第一篇把KL的variational formula扩展了一下，定义了 https://www.zhihu.com/equation?tex=G_%5CGamma+%28%5Cmu%7C%7C%5Cnu%29+%3D+%5Csup_%7Bg%5Cin%5CGamma%7D+%5Cleft%5C%7B%5Cint_S+gd%5Cmu+-%5Clog+%5Cint_S+e%5Eg+d%5Cnu%5Cright%5C%7D 和 https://www.zhihu.com/equation?tex=W_%5CGamma%28%5Ceta%29+%3D+%5Csup_%7Bg%5Cin%5CGamma%7D+%5Cint_S+gd%5Ceta ，然后导出了一个inf-conv的等式： https://www.zhihu.com/equation?tex=G_%5CGamma%28%5Cmu%7C%7C%5Cnu%29+%3D+%5Cinf_%7B%5Cgamma%5Cin+P%28S%29%7D+%5C%7BKL%28%5Cgamma%7C%7C%5Cnu%29+%2B+W_%5CGamma%28%5Cmu-%5Cgamma%29%5C%7D 。其实这个等式的证明思路就是惯用的凸分析的思路，意义是把KL和Wasserstein-type distance联系起来，重点就是通过改变函数的空间来改变定义，通过Wasserstein-type的variational formula的独特形式（线性）来和空间indicator函数的dual取得联系。第二篇就更反直觉一点，是把f-divergence的variational form扩展了。原来的形式是 https://www.zhihu.com/equation?tex=D_f%28Q%7C%7CP%29+%3D+%5Csup_%7Bg%5Cin+M_b%7D+E_Q%28g%29+-+E_P%28f%5E%2A%28g%29%29+%3D++%5Csup_%7Bg%5Cin+M_b%7D+E_Q%28g%29+-+%5CLambda_f%28g%29+...%281%29 ，以及 https://www.zhihu.com/equation?tex=%5CLambda_f%28g%29+%3D+%5Csup_%7BQ%7D+E_Q%28g%29+-+D_f%28Q%7C%7CP%29 。这里的定义是 https://www.zhihu.com/equation?tex=%5CLambda_f%28g%29+%3D+%5Cinf_%7Bv%5Cin%5Cmathbb%7BR%7D%7D+%5C%7Bv+%2B+E_P%28f%5E%2A%28g-v%29%29%5C%7D。在KL的特殊情况下，是cumulant generating function，这两个式子分别是Donsker-Varadhan variational formula 和 the Gibbs variational formula，也就是KL和cumulant generating function的对偶关系。和上一篇paper相似的是，把函数空间变换成，然后得到inf-conv的式子 https://www.zhihu.com/equation?tex=D_f%5E%5CGamma%28Q%7C%7CP%29+%3D+%5Cinf_%7B%5Cgamma%7D+%5C%7BD_f%28%5Cgamma%7C%7CP%29+%2B+W%5E%5CGamma%28Q-%5Cgamma%29%5C%7D 。这样就把f-div和W-dist取得联系，然后分析optimizer、asymptotic behavior等等。之前看到过Dupuis类似的结论，总是百思不得其解的定义里为什么用v的shift，这个想法怎么得到的。看了这个文章发现是因为如果把f变成 https://www.zhihu.com/equation?tex=f_c+%3D+f%2Bc%28x-1%29 后，https://www.zhihu.com/equation?tex=D_f 的值不变，所以它的dual应该也对这种变换保持不变，因此，把 https://www.zhihu.com/equation?tex=E_P%28f%5E%2A%28g%29%29 换成 https://www.zhihu.com/equation?tex=%5Cinf_c+E_P%28f_c%5E%2A%28g%29%29 也就是的定义。这种stat的对偶关系之前就让我很着迷，但即使看了这两个paper之后，依然觉得technical的部分大于直觉的部分。
8-21 最近真的很艰难，日更完全是奢望。看了两篇Amari的文章，分别是“Information Geometry and Its Applications: Convex Function and Dually Flat Manifold” 和 “Information geometry“。话说follow了一下他最近在做什么，都是神经网络相关的文章。从他的文章中获得了一些DG定义背后的意义。比如说affine connection是为了在两点的tangent spaces中间做一个linear mapping（曲线不同点的tangent space并不平行，所以如果要比较不同点的tangent vector的话，需要这样一个map，叫parallel transport），Levi-Civita connection就是唯一的保存metric不变的affine connection（就是如果X1和X2 map 到 Y1和Y2，那么 https://www.zhihu.com/equation?tex=%5Clangle+X_1%2CX_2%5Crangle+%3D+%5Clangle+Y_1%2C+Y_2%5Crangle ）。有了connection之后，就可以定义covariant derivative并列出geodesic（切向不变）的微分方程。如果是Levi-Civita connection，不仅切向不变，而且geodesic是两点之间长度最短的曲线。接着可以定义curvature（这里的curvature和convex geometry的curvature等价嘛？）。
除了这些DG的基本intuition之外，更重要的是information geometry的脉络。主要是parametrized prob space（exp和mixed）的primal和dual的坐标表示。之前理解凸分析算法的时候，已经觉得primal-dual坐标变换很神奇（一些算法在dual空间上看很有意思），这里不仅仅是它俩的坐标变换，而是加上了manifold本身变成了一个三角的关系，manifold是主要对象，坐标仅仅是坐标。其实有参数的所有对象都可以这样搞，把参数（光滑的话）看成坐标系，用DG的思路研究抽象空间上的tangent space、curve、metric等等，研究和坐标无关的不变量，这些思路做物理的应该很熟。。另外，又让我想到prob density的坐标变换公式，只不过这里是对参数坐标变换，而density的公式是对prob space坐标变换。回正题，有趣的点在于，dually flat Riemannian manifold和dual convex potential functions有对应关系，potential fn可以定义dually flat R-mnfd不奇怪，但是dually flat R-mnfd一定会对应potential fn还挺神奇的。接下来就是耳熟能详的metric、divergence、Legendre transform等等的关系。其中他指出，coordinate可以混用，i.e., https://www.zhihu.com/equation?tex=%28%5Ceta_1%2C%5Cdots%2C%5Ceta_p%2C+%5Ctheta_%7Bp%2B1%7D%2C%5Cdots%2C%5Ctheta_n%29 也是一个坐标，这一点和物理的思路也很像（这也是为什么我一直学不好热力学那块的物理的原因，因为坐标变换对物理学家很自然。。），这种坐标混用的思路不知道能不能用来设计算法。另外，paper里给出了Fisher information的一个意义：它是唯一的R-metric which is invariant under x transform and https://www.zhihu.com/equation?tex=%5Ctheta transform。中间的垂直相关的几个定理暂时没什么感觉。最后给出了application，想看的方向包括和EM的关系，以及和barrier fn的关系等，下次再看。
8-25 感觉这个低谷期可能过去了。收拾好心情，好好做事吧。这几天看了一篇文章，“Information Geometry and Primal-Dual Interior-point Algorithms”。是接着information geometry讨论和convex optimization algorithm的关系。这个和我之前从mirror descent 方法学到的对优化算法做change of variable后理解的那个思路应该是一个思路，但同时又融合了ODE的思路，挺有趣的。简言之，这个paper是考虑了采用某一种barrier function https://www.zhihu.com/equation?tex=%5CPsi （主要的特性是 https://www.zhihu.com/equation?tex=%5CPsi%28tx%29+%3D+%5CPsi%28x%29+-+%5Ctheta+%5Clog+t ），考察了这种barrier function下对primal 和 dual 问题的interior point方法的trajectory，计算了这两个traj的ODE形式（另，二阶导数和embedding curvature有关，这个和之前几个curvature的定义有关系吗？），提出了算法（迭代地走一步ODE再做一步优化），并分析了算法的步数估计（用information geometry的统计量估计的）。虽然从中没有得到我想要的intuition和关联，但是去掉细节之后这个paper算是总结了我之前零零散散领悟到的一些观点：1. 一个优化算法，在dual空间上也许更好理解。从另一个角度看，在设计算法的时候除了考虑primal 空间之外，还可以考虑dual 空间：在dual空间上做迭代后在primal 空间上会产生怎样的算法？优势是什么？从DG的角度，可以看成在manifold上沿着某条曲线走，在不同坐标系下会产生不同的曲线，不同离散的格式会导出不同的算法。那么，会不会有很多不同的算法其实只是不同坐标系下不同的离散而已？2. 优化和ODE的结合。这个在那几篇ODE角度理解Nesterov加速算法的paper里也有体现。很多算法是显性格式给出的，但是可以有不同的理解方法，比如每一步其实是解一个优化问题（或解优化问题的第一步），或者这些格式是某个ODE的离散，而ODE对应着另外一些模型比如optimal control问题。这些不同的思路在我看来就像是optimal control算法里那些先离散再优化和先优化再离散的区别一样，在把问题变成可计算的过程中有很多步会导致误差，改变这些步数的顺序会给出不同的算法。可以离散的两种重要的模型就是优化模型和ODE模型，因此解一个问题可以从找到等价优化模型/ ODE模型入手。说了半天其实不就是图像处理的常用套路吗。。。感觉完全不fancy。。。
8-28 打脸，人生有（应用）数学真是太好了。这两天接着读Amari的文章，然后才发现这位不是最近赶热点开始做NN，而是在我出生前就做过NN了。。。又想起之前和朋友的聊天，他说觉得沮丧，因为NN现在做的idea们基本上个世纪就有了。言归正传，这次的paper是EM相关，“information geometry of the EM and em algorithms for neural networks"，94年的paper，老paper有很多值得读的。这篇从abstract就一直在tease，让人十分想读，关于EM和em、关于NN的关系、关于KL相关的优化、关于mixture of experts。不过统计方面的想法，我到现在都没什么头绪，主要是没有掌握住有信息缺失的时候如何处理的这种建模的思路吧。这篇文章的假设是，有一个underlying prob manifold，在这个里面有两个submnfd，M和D。M指的是我们用的model的集合，D指的是可以表示data的那些model的集合。这两个集合并不一定有交集，即data不一定可以用我们的model表示。问题是，如何找到适合的模型和隐藏变量，适合的模型是和数据相近的模型，隐藏变量是和模型相近的数据变量，所以就是寻找M和D之间相近的地方。em很好理解，就是 https://www.zhihu.com/equation?tex=%5Cmin_%7BP%5Cin+M%2C+Q%5Cin+D%7D+KL%28Q%7C%7CP%29 【为什么不反过来？把KL换成其他div会变成什么算法？】，算法就是交替优化Q和P。EM就复杂一些，统计一些，E（expectation）是算隐藏变量的方法，就是用conditional expectation；M就是用隐藏变量+数据算mle求P。文中把EM算法的E写成等价形式 https://www.zhihu.com/equation?tex=%5Cmin_%7BQ%5Cin+D%7DKL%28F%5E%7B-1%7DQ%7C%7CP%29 ，这里的函数F是从（data，隐藏变量）到（data，conditional exp）的函数，这地方挺奇怪的。然后M步和m步是一样的。所以EM和em的区别就在于E和e步里面的。上次说优化和ODE的联系是一个理解离散格式的方式，那么这个文章就是用优化和一些统计estimator来理解算法。这种联系也很重要，但是更加不明，唯一有印象的文章是说Bayesian estimator是某个形式的优化问题的解。另外这个文章提了一句，传统NN可以看出stochastic NN的expectation，这个也很有意思，现在没怎么见有人这样做，也许是stochastic NN很难计算，所以不知道这种联系有什么用。但是更加狂放一些，stochastic NN的其他Bayesian estimator会给出什么？只是可能很难算。。
8-29 今天继续EM和variational form的关系。首先稍微了解了一下EM算法，更新的EM算法和昨天看的并不一样，E这一步变成了对likelihood做conditional expectation，而不是对parameter做conditional expectation，这两种应该不等价，前一种有点类似Bayesian estimator的思路，是用distribution来代替parameter estimation。Amari的书里说，这种新版的EM算法和em等价，改天研究下为什么。为什么换了一下E step就可以吧昨天说的给去掉，说起来到底代表什么也没搞懂，其实一头雾水。。。新的EM每一步可以写成一个优化问题： https://www.zhihu.com/equation?tex=max_%7B%5Cxi%7D%5Cint+p%28h%7Cx%2C%5Cxi%5Ek%29%5Clog+p%28x%2Ch%2C%5Cxi%29dh ，x是data，h是hidden variable， https://www.zhihu.com/equation?tex=%5Cxi 是model里的参数。这个角度看，是max entropy的fixed point方法。但是这种EM和em的关联就很神奇，能把一个非凸优化变成min-min problem（em角度），这个min-min对各自的变量是凸的（jointly凸吗？），这种转化是个很好的证明收敛性的思路，但是很难想到，有套路吗？
这个套路让我想起之前烂尾的一个东西，那个东西的证明思路也是这样。于是又把那时候的两个文章翻出来看了看，即“Variational Characterizations of Local Entropy and Heat Regularization in Deep Learning“ 和 “Deep relaxation: PDEs for optimizing deep neural networks"。这两个文章都很神奇，都有一种玄而又玄很fancy的感觉，但是细想又一头雾水，其实这下面大概率有值得挖的东西，只不过时机还没到。第一篇把 f 的优化问题relax 成两种形式，log partition fn 和 convolution with heat kernel，而relax过的函数有variational form。前一个函数的variational form是KL的对偶关系给出的，后一个函数是一个很神奇的对偶，不知道怎么凑出来的。和EM的关联是，前一个函数的coordinate descent其实和EM很像，但是这个的model里面并没有data和hidden variable之类的。那么这种相似点从何而来？也许不需要从统计的模型出发，而是从纯优化的角度，给出一个可以结合这两种问题的框架，不过需要认真看一下证明就是了。第二个函数的算法的第二步和第一个算法的区别仅仅是在KL的两个变量换了位置，这也很神奇。第二篇文章，Osher的，比较偏重Gibbs distribution、PDE和SDE多过优化的思路和statistics，那个再看一遍也觉得和现在的主线关联不大，其实是发散很广的枝干，从长计议。
这里的重点在于，优化算法、优化问题的各种等价形式（以variational form得到）。这些不同paper里的min-min问题都有相似的形式：一项+KL，其实Paul的variational form也是这个形式，或许可以从这个形式下手呢？明天继续。
8-29 哈哈终于做到一天两更了（大雾。昨天所有的疑惑都来自于，我是从information geometry入的EM，EM算是statistical estimation里面的东西，我完全不懂，就像是一只松鼠从一棵树跳到另一棵树的最边缘的枝桠上，肯定会觉得摇摇欲坠，最好的办法是找个教程从根开始了解一下。于是今天找到了一个lecture notes “The EM Algorithm: Theory, Applications and Related Methods”。不是什么太有名的教程，但是网上这方面的内容真的不多，又是一个成(guo)熟(qi)领域吗233. 但是这个教程里我今天看到的部分基本解决了我所有的疑惑，没解决的也当作疑惑在里面提出了，有如下几点：
首先，昨天说有很多不同的模型，都长得很像，是KL + 某一项的形式，它们的收敛性证明也很类似。这篇notes里给出了一个优化角度的统一框架，以及这个框架的收敛性证明，不过那个证明其实很简单。说到这吐槽一句，其实优化也是这样的，无数的算法，每个算法都有一个收敛性分析（大多是用Lyapunov函数分析，这一块我完全搞不懂，因为构造李雅普诺夫函数对我来说毫无概念，似乎是凭空构造的，或者是做多了证明之后有看到某一项就知道对应什么函数的经验），但这些算法之间的关系有的时候其实很微弱。如果有一个大的框架可以统一就好了，这样在这个框架下的算法都不用重新证明收敛性收敛速度什么的，而且提出新算法的时候也可以有迹可循。之前的那些优化和ODE、PDE、DG等等的关系都是为了这个目的，可惜暂时没看到什么可实施性。言归正传，notes里提出了Auxiliary-Function (AF) Methods，就是为了优化 f 而每一步解 https://www.zhihu.com/equation?tex=%5Cmin+f%28x%29+%2B+g_k%28x%29 ，这里的 https://www.zhihu.com/equation?tex=g_k 是nonnegative并且满足 https://www.zhihu.com/equation?tex=g_k%28x_%7Bk-1%7D%29%3D0 。有这两个条件，可以证明这个算法是decreasing的，因此函数值收敛（至于收不收敛到正确值、 https://www.zhihu.com/equation?tex=x_k 收不收敛就还需要其他条件），证明就是简单计算。这种思路是优化算法里面的“每一步解一个优化问题”的思路，即，下一步要在上一步的附近找一个函数值小的，gradient descent也可以用这种思路表示。【这边插一句，凸优化算法都是这样local的算法，放到非凸的时候就容易陷入local min，非凸很多都是stochastic相关的，感觉最近看的这些应该用不到非凸上去。但是我依然希望通过几何的角度，把某一类的非凸问题升维或者换元变成凸函数，不用sampling而是用凸分析来做，不知道有没有人做过，我没有看到类似的文章】。另外，notes里提出了AF的三个子问题，一个是Alternating Minimization (AM)，其实就是coordinate descent，即优化 https://www.zhihu.com/equation?tex=f%28x%2Cy%29 的时候，交替优化x和y，这种算法一直被我老板看不上，因为收敛性没保障，从这个文章知道函数值的收敛性有保障的，不过要check一个不等式，这个不等式对jointly convex Bregman div自动成立，比如KL。第二个子问题是proximal minimization algorithm (PMA)，指每一步解 https://www.zhihu.com/equation?tex=min_x+f%28x%29+%2B+d%28x%2Cx_%7Bk-1%7D%29，这里d是一个“distance”，原文打了引号，我觉得divergence即可，之所以叫proximal是因为如果d是普通的quadratic的话，就会变成proximal point algorithm。notes里证明了这两个子问题其实是等价的，等价性通过把AM中的y写成x的函数来减少一个变量、PMA中 https://www.zhihu.com/equation?tex=x_%7Bk-1%7D 写成y来增加一个变量，这种等价性感觉还是technical了一点，没有什么直觉【也许深挖会和升维的思路有关？】。第三个子问题是majorization minimization (MM)，其实和另两个问题也是等价的，就是每一步解 https://www.zhihu.com/equation?tex=min_%7Bx%7D+g%28x%7Cx_%7Bk-1%7D%29 ，这里g是满足 https://www.zhihu.com/equation?tex=g%28x%7Cy%29%5Cgeq+f%28x%29%2C+g%28x%7Cx%29%3Df%28x%29 的函数，其实就是PMA换了个notation，不过印象中Jordan搞的ELBO是不是就是这个思路，当时因为KL的variational form去看的，结果全都是technical的不等式，毫无直觉，也许也有关系，改天再看看。
套用这个结构，f对应的是 https://www.zhihu.com/equation?tex=-p%28x%7C%5Ctheta%29 ，另一项是 https://www.zhihu.com/equation?tex=p%28x%2Ch%7C%5Ctheta%5E%7Bk-1%7D%29 和 https://www.zhihu.com/equation?tex=p%28x%2Ch%7C%5Ctheta%29 的KL，这样出来的算法就是某一种EM。这是就显现出EM难学的原因，有不同版本的EM，每一步解不同的expected log likelihood，比如wiki上的 https://www.zhihu.com/equation?tex=%5Cmin_%7B%5Ctheta%7D%5Cint+p%28h%7Cx%2C%5Ctheta%5E%7Bk-1%7D%29%5Clog+p%28x%2Ch%7C%5Ctheta%29dh (这种也是之前Amari书里那一种)，notes里的https://www.zhihu.com/equation?tex=%5Cmin_%7B%5Ctheta%7D%5Cint+p%28h%7Cx%2C%5Ctheta%5E%7Bk-1%7D%29%5Clog+p%28h%7C%5Ctheta%29dh，还有上面的优化结构对应的https://www.zhihu.com/equation?tex=%5Cmin_%7B%5Ctheta%7D%5Cint+p%28x%2Ch%7C%5Ctheta%5E%7Bk-1%7D%29%5Clog+p%28x%2Ch%7C%5Ctheta%29dh。文中给出了几种后两者等价的情况，比如x｜h 和theta无关，或者h包含x和另外的hidden variable。这一块就是我每次统计之所以学不好的原因，有太多的概率，条件概率joint、marginal等，到底modeling的时候应该用哪一种，就很混乱，尤其是在有了贝叶斯框架之后，parameter也加入了战场，更乱了。。另外就是，从这个结构给出的AM的setup应该并不是前几天看到的那种em的角度，更可能（在新变量y是prob measure的情况下）导出wiki上的max-max procedure，因为对y的那一步coordinate descent是trivial的。因此，如何把这种问题写成em的形式，依然没有解决【而且我很好奇这种思路能不能推广】。
另外的收获，就是从统计或者modeling的角度认识了一下这个算法。之前都是从NN的模型开始想的，中间的neuron是hidden variable，input-output是data。这本书是完全从data的视角，只给data如何设计变量和模型，是一个modeling的视角。如果只有data，假设了一个model，第一个想法是mle。EM是在mle不好算的时候，找一个好算的“preferred data”，这个就是EM中的hidden var。这个时候想要对于好算的h做mle，但是没有h的data，于是退而求其次，把log likelihood做一个针对现有data的expectation【至于为什么是expectation不是别的什么，就是modeling和可计算性的问题了，也许可以有别的什么，但是太远了】，然后对这个expectation做mle。这样想其实顺很多。
另外，最开始的时候作者举了CT的成像modeling的例子，用完全discrete的modeling（每个photon当成一个小球，发射到每个位置有特定的概率），和用poisson distribution做出来的modeling的EM算法是一样的。最开始的时候，有人把好的结果归结成准确的物理模型（poisson），但其实好的结果是因为EM的收敛性。这就很有趣，究竟什么样的模型可以得到好的结果。discrete的那个modeling肯定是不准确的，但是这个模型里的什么特点让它的EM和一个准确的模型的EM是一样的？也许换个算法这两个模型给的结果就不同了。那么，怎样的算法需要怎样的“模型特质”？如果知道了这点，就可以在modeling的时候有的放矢，精简不怎么重要的“特质”。这里就是玄学的部分了。。。
8-30 今天是无聊的过度。看完了昨天的那个lecture notes，剩下的部分都是technical的细节，就是说明各种算法都在这个框架下，比如Osher的（是叫Bregman descent吗？忘记名字）算法也在这框架里面。在计算中稍微有趣的点就是如何从等式写出对应的优化问题，这种对应当然是一对多。比如forward-backward方法，等式是 https://www.zhihu.com/equation?tex=%28x%5E%7Bk-1%7D-%5Cgamma+%5Cnabla+f_2%28x%5E%7Bk-1%7D%29%29-x%5Ek+%5Cin+%5Cpartial+%28%5Cgamma+f_1%29%28x%5Ek%29 ，既可以写成FB方法原本的形式： https://www.zhihu.com/equation?tex=x%5Ek+%3D%5Ctext%7Bargmin%7D_x%5Cgamma+f%28x%29+%2B+%5Cfrac%7B1%7D%7B2%7D%5C%7Cx+-+%28x%5E%7Bk-1%7D+-+%5Cgamma+%5Cnabla+f_2%28x%5E%7Bk-1%7D%29%29%5C%7C%5E2 ，又可以写成Bregman div的形式： https://www.zhihu.com/equation?tex=x%5Ek%3D%5Ctext%7Bargmin%7D_x+f_1%28x%29%2Bf_2%28x%29+%2B+%5Cfrac%7B1%7D%7B2%5Cgamma%7D%5C%7Cx-x%5E%7Bk-1%7D%5C%7C%5E2+-D_%7Bf_2%7D%28x%2Cx%5E%7Bk-1%7D%29 。接着回归了Amari的书，试图看一下昨天没理解的EM和em的等价有什么深刻的证明，结果完全不深刻。。因为e那一步也是trivial的。。即，得到的data上的distribution就是上一步参数给的distribution。其实细看，wiki中的max-max问题稍微变形一下就是em的形式。。难道这种把一个变量的优化问题变成两个变量的都是这种套路？那coordinate descent中必有一步是trivial的。。另外还有一些满头雾水的KL、exp family、Bregman div的公式，暂时没看出什么intuition。不过在读这些东西的中间突然想起之前看的一篇文章“Entropic optimal transport is maximum-likelihood deconvolution"，明天再翻出来看一下，还有Amari那本书最后有一些应用我也想看一下，比如和Bayesian、stochastic、barrier function的关系之类的。明天再说吧～
8-31 八月的最后一天，开学在即。情绪真的会影响看书的领悟力，所以保持一个积极但是平稳的心态比较重要。不过真正难度和有趣度都在sweetpoint上的内容能平复心态，所以找到合适的内容也很重要。今天组会，老板又一次强调了“看清计算机硬件的发展趋势，利用这些硬件做出快速算法”的重要性，自然，在应用数学的领域，真正快速的解决问题才是重点，一个结果又快又好但是原理不明的方法和数学很fancy但是很难应用/很难懂的方法，永远是前者有更广泛的应用，这是应用数学的本质决定的。因此，想要在这个领域混的好，迅速的找到新的东西，并且把简单的思路用在上面，勤奋的尝试，这些都是很重要的。他说，不管你是不是hate it，这个就是客观事实。Osher博士的时候做纯数，正因为看到了他做的领域的颓势，所以转到了应用成了大佬。George在NN还没在科学计算火起来的时候，用了最自然的思路，带起了一个领域。我确实hate it，十分的格格不入。老板说，找到一个空间很重要。在应用数学做，喜欢数学却不喜欢应用，真的是本末倒置，毫无空间。稍微好一点的是跟随热点做一点eps改进，可以生存但只是生存。很沮丧，没法说服自己做的是好的有用的研究，就像我学长，他告诉我即使他在Osher那边做的很好，但是因为他自己没法说服自己，所以也没法说服别人。如果在这一代，算力提升的速度超过了用深刻的数学慢慢演化成算法的速度，靠着计算机速度的提升，在新的硬件上用最基本的数学设计的算法比不适用于新的硬件的很数学的算法要快很多的话，那真的是很有用但是很无聊的事情。也许我是错的，但是我对这种”大多数情况下不需要很数学的东西“（可能是事实）的观点感到本能的反感。
言归正传。今天按照昨天的计划，看了Amari书里对贝叶斯、stochastic、barrier fn的应用，以及那篇论文。贝叶斯那块主要是restricted Boltzmann machine（RBM），算是补了一下NN的前辈历史。RBM是一个随机的模型，假设了一个data和hidden var的joint distribution。虽然和现在NN的图模型很像，即层与层之间有相关性，层内部不相关，但是其实从解决的问题的角度和GAN比较接近，都是希望找到一个distribution来approximate sampled data，而且做法都是最自然的想法：用KL做projection的想法，min KL(data || model)，等价于mle。但这个最自然的想法不太好算，RBM和GAN依靠自身的模型的特点找到了简化算法的思路。GAN相当于用NN做change of var，而change of var的难度在于变换后的density fn 比较不好算，因为需要求导再求det，因此简化的思路是不要直接求KL而是用variational form把原先的优化问题变成一个saddle point问题再优化硬解。这里variational form里面是一些积分，而对push-forward measure的积分非常好算， https://www.zhihu.com/equation?tex=%5Cint+g%28y%29+df_%5C%23%5Cmu%28y%29+%3D+%5Cint+g%28f%28x%29%29+d%5Cmu%28x%29 。所以对push-forward measure的计算来说，尽量算expectation，不要直接用density。RBM的难点不同，它的joint density是由model给出的，但是marginal density需要积分，不太好算，因此简化的思路是把marginal的KL变成joint 的KL，然后用em，其中e-projection是trivial的，因为 https://www.zhihu.com/equation?tex=argmin_r+KL%28q%28v%29r%28h%7Cv%29+%7C%7Cp%28v%2Ch%29%29+%3D+p%28h%7Cv%29 。其实这种trivial的minimizer对KL很常见，比如 https://www.zhihu.com/equation?tex=argmin_r+KL%28p%28v%2Ch%29+%7C%7C+q%28v%29r%28h%7Cv%29%29+%3D+p%28h%7Cv%29 ， https://www.zhihu.com/equation?tex=argmin_q+KL%28p%28v%2Ch%29+%7C%7C+q%28v%29r%28h%7Cv%29%29+%3D+p%28v%29 ，不过 https://www.zhihu.com/equation?tex=argmin_q+KL%28q%28v%29r%28h%7Cv%29+%7C%7C+p%28v%2Ch%29%29 好像不是p(v)，而是 https://www.zhihu.com/equation?tex=%5Csim+p%28v%29e%5E%7B-KL%28r%28%5Ccdot%7Cv%29+%7C%7C+p%28%5Ccdot%7Cv%29%29%7D 。虽然这个思路很好很清晰，但是计算的时候是等价的，所以还是在原来的marginal的KL上算gradient descent，经过计算后是两个expectation的差，于是用MCMC算expectation。其他两部分内容比较简略。stochastic relaxation是说instead of 求 https://www.zhihu.com/equation?tex=%5Cmin_x+f%28x%29 ，我们求 https://www.zhihu.com/equation?tex=%5Cmin_%7B%5Cxi%7D+E_%7Bp%28x%7C%5Cxi%29%7D%5Bf%28x%29%5D ，这是把delta distribution generalize成其他family的操作，日后开stochastic的坑的话再详细讲吧。其他优化的部分是说interior point method和mirror descent在dual space里面理解起来更简单，这个日后开优化的坑再细说吧2333.
最后，看了“Entropic optimal transport is maximum-likelihood deconvolution”，依然没有比上次看懂的更多，感觉只是利用了log partition fn和KL的对偶关系，mle可以看成优化log partition fn，从而用对偶关系变成了min-min问题，而对偶关系里面 https://www.zhihu.com/equation?tex=E_Q%5Bg%5D 那一项又可以和最优运输扯上关系，不知道有什么用。其实Paul的paper里面和最优运输扯上关系也是因为那个线性项 https://www.zhihu.com/equation?tex=E_%7B%5Cmu-%5Cnu%7D%5Bg%5D ，也不知道有什么用。总之，最近这个坑看着看着就看到统计去了，有一些收获吧，但是之前迷惑的地方还是没有解决。明天是不是可以换个坑了。
页:
[1]