双信封悖论和围城效应

双信封悖论和围城效应
from 阅微堂 by zhiqiang

问题：你有两个信封可以选择，每个信封里有一定数量的钱，已知其中一个信封里的钱是另外一个信封的两倍。你可以选择一个信封，打开之后你能看到其中的钱的数量。现在你可以选择是否更改你的选择。

推断：你应该更改你的选择

1. 假设你打开信封后发现里面钱的数量为A。
2. A是较小的钱数的概率为1/2，为较大的钱数亦为1/2。
3. 如果A是较小的钱数，则另一个信封里钱数为2A；
4. 如果A是较大的钱数，则另一个信封里的钱数为为A/2。
5. 所以另一个信封里的钱数的期望为 E = 2A×1/2+A/2×1/2=5A/4，大于A。
6. 你应该更换你的选择。

想想看，这个问题和推断是不是有点像围城效应？

很显然，上面的推断结果是有问题的。关键在于第二条，如果上面推断中的第二条成立的话，我们假设P(A)为两个钱包里的钱数为（A/2，A）的概率，那么将有P(A)=P(2A)，从而有一个定义在一个无穷集上的均匀分布，这是不可能的。

上面这个问题以前就讨论过，最近一个同学问起这个悖论的变种：

问题：你有两个信封可以选择，每个信封里有一定数量的钱，已知其中一个信封里的钱是另外一个信封的两倍。而且两个信封里的钱的数量是 (10^n,10^{n+1})的概率是2^{-n}，其中n=1,2,\cdots, +\infty。你可以选择一个信封，打开之后你能看到其中的钱的数量。现在你可以选择是否更改你的选择。

推断：你应该更改你的选择

1. 假设你打开信封后发现里面钱的数量为A。
2. 如果A=1，另外一个钱包有10块钱，你应该更换你的选择。
3. 如果A>1，另一个钱包为10A的概率为1/3，有A/10块钱的概率为2/3。
4. 另一个钱包的期望钱的数量为17A/5，大于已选的钱包的钱数A。
5. 你应该更换你的选择。

这个推断几乎没有问题，一句话的总结就是，在一个期望无限收益的游戏里，玩家不可能得到满足（达到期望值）。

商务信函中 as opposed to 的用法

　　最近在商务信函中看到 as opposed to 出现频率比较高，于是查阅了下资料，这个词组的含义是“相对于..., 不是...”，要理解也不困难，举个简单的例子: 甲乙两人对话，甲说，这是一头牛，乙说，这是一头羊，而不是一头牛，口语化或者 casual style 说起来就是: It's a lamb, not a cow. 用公务的句式可以写成: It's a lamb, as opposed to a cow.
　　这里要说明的是，as opposed to 多是用于会话或信函来往中一方对另一方的反馈，你必须是清楚地明白某件特定的事，而非对方所提出的那件，就好像乙知道这是只羊，而非甲说的牛。可见，在没有对话的互动情景下就不必使用 as opposed to， 比如甲自言自语说，这是头驴，不是马，这时候就不需要说 It's a mule, as opposed to a horse，因为这句话完全可以有更多种说法，比如，这是头驴，不是骡子，或者，这是头驴，不是羊，或者，这是头驴，不是牛，等等等等，有多少飞禽走兽就 会有多少种说法，也就是说没有特定的对比对象，在这样的情况下， It's a mule, not a horse 就足够了。
　　Please call me POPO, as opposed to Plod:)

Java Related

----------------------------------------------------

1.参数by value 非 by reference

2.不变的data 和 object reference用final

3.缺省所有的non-static 函数都可overridden

不允许客户overridden的函数用final

4.array与vector 之间要慎重

array可以容纳 primitive type 也可容纳 object reference

5. polymorphism优于instanceof(运行期确定对象的隶属class)

6.必要时才选择instanceof

7.一旦不需要object reference就 = null

8.不要总依赖java garbage collection

"内存问题纯属庸人自扰"--------------掌嘴。

Runtime rt=Runtime.getRuntime();

long mm=rt.freeMemory();

System.out.println(mm);

//.........

System.gc();

//..........

System.out.println(mm);

9. reference vs. primitive means primitive vs. wrapper

10. == vs. equals()

不要依赖equals()的缺省实现

11. overridden equals()要深思熟虑

12.overridden equals()时优先考虑getClass();

13.调用 super.equals()唤起base class的相关行为

14. equals()中慎用 instanceof

15. 想try/catch置于循环之外

------------------------------------------

Java Performance

1. 把焦点放在 datastruct 和 Algorithm上

2. StringBuffer.append() 优于 String.concat()和+

3.不要依赖 compile-in-time

4.理解运行期Runtime优化技术

5. 将对象的creation cost减至最小

6.尽可能用 stack 变量

Class StackVars{

private int inst_var;

private static int static_var;

void stackAccess(int var){

int j=0;

for(int i=0;i

j++;
}

void instanceAccess (int val){

for(int i=0;i

inst_var++:

}

void staticAccess(int val){

for(int i=0;i

static_var++

}

}
7.多使用static final private 促成 inlining,在编译器被statically resolved

8.instance变量init一次就好

9. primitive vs. wrapper

10.不要用Enumeration 或Iterator 遍历 Vector

<1> Iterator

<2> ListIterator

<3> Enumeration

<4> get() //it's the best

11. 用System.arraycopy()来cp array

12. array vs. Vector和 ArrayList

1 3. 尽量reuse Object

14. 手工优化 javap -c

和机器学习与计算机视觉相关的数学

[转载]
感觉数学似乎总是不够的。这些日子为了解决research中的一些问题，又在图书馆捧起了数学的教科书。从大学到现在，课堂上学的和自学的数学其实不算 少了，可是在研究的过程中总是发现需要补充新的数学知识。Learning和Vision都是很多种数学的交汇场。看着不同的理论体系的交汇，对于一个 researcher来说，往往是非常exciting的enjoyable的事情。不过，这也代表着要充分了解这个领域并且取得有意义的进展是很艰苦 的。 记得在两年前的一次blog里面，提到过和learning有关的数学。今天看来，我对于数学在这个领域的作用有了新的思考。对于Learning的研 究，
1、 Linear Algebra (线性代数) 和 Statistics (统计学) 是最重要和不可缺少的。这代表了Machine Learning中最主流的两大类方法的基础。一种是以研究函数和变换为重点的代数方法，比如Dimension reduction，feature extraction，Kernel等，一种是以研究统计模型和样本分布为重点的统计方法，比如Graphical model, Information theoretical models等。它们侧重虽有不同，但是常常是共同使用的，对于代数方法，往往需要统计上的解释，对于统计模型，其具体计算则需要代数的帮助。以代数和统 计为出发点，继续往深处走，我们会发现需要更多的数学。
2、Calculus (微积分)，只是数学分析体系的基础。其基础性作用不言而喻。Learning研究的大部分问题是在连续的度量空间进行的，无论代数还是统计，在研究优化 问题的时候，对一个映射的微分或者梯度的分析总是不可避免。而在统计学中，Marginalization和积分更是密不可分——不过，以解析形式把积分 导出来的情况则不多见。
3、Partial Differential Equation （偏微分方程)，这主要用于描述动态过程，或者仿动态过程。这个学科在Vision中用得比Learning多，主要用于描述连续场的运动或者扩散过程。 比如Level set, Optical flow都是这方面的典型例子。
4、Functional Analysis (泛函分析)，通俗地，可以理解为微积分从有限维空间到无限维空间的拓展——当然了，它实际上远不止于此。在这个地方，函数以及其所作用的对象之间存在的 对偶关系扮演了非常重要的角色。Learning发展至今，也在向无限维延伸——从研究有限维向量的问题到以无限维的函数为研究对象。Kernel Learning 和 Gaussian Process 是其中典型的例子——其中的核心概念都是Kernel。很多做Learning的人把Kernel简单理解为Kernel trick的运用，这就把kernel的意义严重弱化了。在泛函里面，Kernel (Inner Product) 是建立整个博大的代数体系的根本，从metric, transform到spectrum都根源于此。
5、Measure Theory (测度理论)，这是和实分析关系非常密切的学科。但是测度理论并不限于此。从某种意义上说，Real Analysis可以从Lebesgue Measure（勒贝格测度）推演，不过其实还有很多别的测度体系——概率本身就是一种测度。测度理论对于Learning的意义是根本的，现代统计学整 个就是建立在测度理论的基础之上——虽然初级的概率论教科书一般不这样引入。在看一些统计方面的文章的时候，你可能会发现，它们会把统计的公式改用测度来 表达，这样做有两个好处：所有的推导和结论不用分别给连续分布和离散分布各自写一遍了，这两种东西都可以用同一的测度形式表达：连续分布的积分基于 Lebesgue测度，离散分布的求和基于计数测度，而且还能推广到那种既不连续又不离散的分布中去（这种东西不是数学家的游戏，而是已经在实用的东西， 在Dirchlet Process或者Pitman-Yor Process里面会经常看到)。而且，即使是连续积分，如果不是在欧氏空间进行，而是在更一般的拓扑空间（比如微分流形或者变换群），那么传统的黎曼积 分（就是大学一年级在微积分课学的那种）就不work了，你可能需要它们的一些推广，比如Haar Measure或者Lebesgue-Stieltjes积分。
6、Topology（拓扑学)，这是学术中很基础的学科。它一般不直接提供方法，但是它的很多概念和定理是其它数学分支的基石。看很多别的数 学的时候，你会经常接触这样一些概念：Open set / Closed set，set basis，Hausdauf, continuous function，metric space, Cauchy sequence, neighborhood, compactness, connectivity。很多这些也许在大学一年级就学习过一些，当时是基于极限的概念获得的。如果，看过拓扑学之后，对这些概念的认识会有根本性的拓 展。比如，连续函数，当时是由epison法定义的，就是无论取多小的正数epsilon，都存在xxx，使得xxx。这是需要一种metric去度量距 离的，在general topology里面，对于连续函数的定义连坐标和距离都不需要——如果一个映射使得开集的原像是开集，它就是连续的——至于开集是基于集合论定义的，不 是通常的开区间的意思。这只是最简单的例子。当然，我们研究learning也许不需要深究这些数学概念背后的公理体系，但是，打破原来定义的概念的局限 在很多问题上是必须的——尤其是当你研究的东西它不是在欧氏空间里面的时候——正交矩阵，变换群，流形，概率分布的空间，都属于此。
7、Differential Manifold (微分流形)，通俗地说它研究的是平滑的曲面。一个直接的印象是它是不是可以用来fitting一个surface什么的——当然这算是一种应用，但是这 是非常初步的。本质上说，微分流形研究的是平滑的拓扑结构。一个空间构成微分流形的基本要素是局部平滑：从拓扑学来理解，就是它的任意局部都同胚于欧氏空 间，从解析的角度来看，就是相容的局部坐标系统。当然，在全局上，它不要求和欧氏空间同胚。它除了可以用于刻画集合上的平滑曲面外，更重要的意义在于，它 可以用于研究很多重要的集合。一个n-维线性空间的全部k-维子空间(k
8、Lie Group Theory (李群论)，一般意义的群论在Learning中被运用的不是很多，群论在Learning中用得较多的是它的一个重要方向Lie group。定义在平滑流行上的群，并且其群运算是平滑的话，那么这就叫李群。因为Learning和编码不同，更多关注的是连续空间，因为Lie group在各种群中对于Learning特别重要。各种子空间，线性变换，非奇异矩阵都基于通常意义的矩阵乘法构成李群。在李群中的映射，变换，度量， 划分等等都对于Learning中代数方法的研究有重要指导意义。
9、Graph Theory（图论)，图，由于它在表述各种关系的强大能力以及优雅的理论，高效的算法，越来越受到Learning领域的欢迎。经典图论，在 Learning中的一个最重要应用就是graphical models了，它被成功运用于分析统计网络的结构和规划统计推断的流程。Graphical model所取得的成功，图论可谓功不可没。在Vision里面，maxflow (graphcut)算法在图像分割，Stereo还有各种能量优化中也广受应用。另外一个重要的图论分支就是Algebraic graph theory (代数图论)，主要运用于图的谱分析，著名的应用包括Normalized Cut和Spectral Clustering。近年来在semi-supervised learning中受到特别关注。