在机器学习里常常会需要估计模型的参数，或者更广泛的，从数据中估计某些变量的值。需要多少数据，才能把这些参数估计到什么样的精确程度，是机器学习理论里面最基础的问题之一。这篇博文简单回顾一下一些比较经典的结论。 首先，几个基本的tail-probability不等式，对于任意\(\epsilon > 0\)： Markov不等式：对于任意非负\(X\)，\(p(X \ge \epsilon) \le \frac{\mathbb{E}[X]}{\epsilon}\)。 Chebyshev不等式：\(p(\lvert...

最近的研究需要探索一些exploration-exploitation tradeoff，想找一些理论上的东西，于是开始看Tor Lattimore和Csaba Szepesvári合著的Bandit Algorithms。这是一本写得很深入和全面的书，应该是把bandit问题的方方面面都讲到了。 Bandit问题是一个基本的、经典的关于exploration-exploitation tradeoff的问题。这个问题的设定一般是假定有\(k\)个选项(action)可选，每次选取一个选项\(a\)后可以得到一个该选项对应的回报\(r\)。对于每个选项\(a\)，其会产生的回报\(r\)有随机性，每个\(a\)的回报的分布可能也都不一样。如果允许选择\(n\)次，那么这n次选择的总回报为 \[\sum_{t=1}^n r_t =...

高中解析几何中学过，椭圆的标准方程 \[\frac{x^2}{a^2} + \frac{y^2}{b^2} = 1\] 可以确定一组满足上式的点\((x, y)\)，所有这些\((x, y)\)就构成了一个椭圆。拿到这样一个方程，我们可以观察到\(x\)坐标一定在\([-a, a]\)的范围之内（\(a...

运动是我们可以直接观测到的物理现象，一个物体从一个地方移动到另一个地方，运动的快慢，都是可以观测的。而力则不同，力是一个挺抽象的概念。中学课本里，我们学过“力是物体间的相互作用”，但这个定义本身是很含糊的，相互作用这个词可以有很多模糊的解读，这样的定义仔细想一下其实并不能算是一个很有用的定义。所以力到底是什么呢？ 历史上，伽利略的一个重大贡献是惯性原理：如果一个物体没有受到任何其他物体和环境的影响，那么它将会保持它的运动状态，一直持续下去。如果物体之前静止，那么它会保持静止，如果物体在朝一个方向以一定速度运动，那么它会继续保持那个方向和速度运动。 牛顿进一步提出，如果要改变物体的运动状态，则需要对它施加一定的影响，比如直接推它一把。这就是要对物体施加一个“力”的作用。牛顿提出了三条定律： 如果一个物体没有受到任何其他物体和环境的影响，那么它将会保持它的运动状态，一直持续下去。（即伽利略惯性原理） 物体动量随时间的变化率与其受到的力成正比。 作用力与反作用力大小相等方向相反。 物理上，动量（momentum）定义为质量（mass）和速度（velocity）的乘积 \[p = mv\]...

最近重新对物理起了兴趣，想要再学习一下物理。于是开始看费曼物理学讲义(The Feynman Lectures of Physics)。这是一套诺贝尔奖得主Richard Feynman 60年代在加州理工给本科生教大学物理课时所编的讲义，大学时我也看过第一本讲义中文版的一部分，当时就印象深刻，不过没有全部看完。这次发现加州理工把全书的内容都放在网上了，我平时上下班和抽空的时间断断续续看网页上的英文版，竟然觉得读起来特别有滋有味。 目前看到第二十四章，讨论的内容已经涵盖了很多方面，主要是牛顿力学的内容，也初步涉及了狭义相对论，第二十四章正在讨论震动。我很喜欢的一点是这本书把物理学的各个方面都串起来讲，比如讲到引力，不仅仅是会提到引力的形式\(F=G\frac{Mm}{r^2}\)，同样也会提及电荷之间的作用力的库仑定律\(F=k_e \frac{qq'}{r^2}\)，因为形式相同（同为平方反比定律）物体运动的规律在这两个定律下完全相同。类似的，讲到引力场和势的时候，同样可以推广到电场和电势。这本书还有一个吸引我的地方是讨论一个物理现象时重视物理原理的思考，而非数学上的严谨和形式化。这和我之前所学习的物理很不一样，我自己之前在中学和大学所学的物理通常是将物理原理的数学形式介绍出来，然后注重于通过数学推导演绎出各种结论。数学固然有它的魅力，但归根到底物理是一门科学，注重理论能够解释实际、能够应用于实际，能够实验验证的理论才是好理论。所以，物理原理和物理思想的发展是很重要也是我之前比较缺失的一个方面。 另一方面，数学形式和推导提供的严谨逻辑也能帮我们认识到什么是根本的规律，什么是衍生的规律。一个规律越“根本”，它就能解释更多的东西，也同样代表了我们对事物认识的更深入，数学形式和推导能帮助我们认清这些。在我们现有的认识里打下坚实的基础。...

最近看一部物理书，里面讲到一些关于引力的问题。涉及到不少和圆、球相关的计算。好久都没有做过基本的积分计算了，把一些结果和推导总结在这里。 首先是关于常数\(\pi\)的定义。数学上我们接触到\(\pi\)最开始是圆周率的概念，它是圆周长和直径的比率：若一个圆的半径是\(r\)，直径\(d=2r\)，周长为\(C\)，那么圆周率\(\pi\)定义为 \[\pi = \frac{C}{d} = \frac{C}{2r}\] 这个式子是常数\(\pi\)的一种定义，但它同时也反映了一个并没有那么简单的规律，那就是：一个圆，不管它有多大，它的周长和半径（或者直径，这里只用半径因为直径就是半径的2倍）的比率是一个固定的常数！为什么圆的周长和半径的比率是一个常数呢？这周长和半径说到底是两个不同的量，他们之间竟然有这么简单的线性关系，其实想想还挺奇妙的。 要证明这一点，可以从圆的定义出发，在二维平面上到一个定点距离相同的点构成一个圆。以圆心为原点，半径为\(r\)的圆上的点\((x, y)\)满足...