2014年8月14日星期四

ML vs. MAP vs. Bayesian Inference

Ref:http://www.xperseverance.net/blogs/2012/11/1396/
1. 极大似然估计(Maximum likelihood estimation)
假设有一堆独立同分布数据X1,…,Xn,其PDF为p(x;θ),其中θ为模型参数,则其似然函数为:
Ln(θ)=∏i=1np(Xi;θ)
而极大似然估计就是要找到参数θ,使得似然函数的值最大。这意思就是找到一个参数θ,使得使用分布p(x;θ)来估计这一堆数据Xi的效果最好。
为啥捏,因为假设X都是离散值的情况下,Ln(Xi;θ)表达的含义是:从参数θ通过模型p(x;θ)产生这一堆数据的概率(把所有单个数据产生的概率乘起来就是产生这一堆数据的概率)。所以p(x;θ)=Pθ(x={Xi}),那么如果当有两个参数θ1和θ2时,Pθ1(x={Xi})>Pθ2(x={Xi}),则说明θ1更好的描述了这组数据,因此要找到一个θ使得整似然函数的值最大!
所以只要将似然函数对θ求导,就可以找到这样的θ。
例子:求N次伯努利分布的最大似然估计:
Bern(x|μ)=μx(1−μ)1−x
L(X|μ)=∏i=1NμXi(1−μ)1−Xi=μS(1−μ)N−S, 其中S=∑i=1NXi
将logL(X|μ)对μ求导得 Sμ−N−S1−μ=0
得μ^N=1NS=X¯N
2. 极大后验估计(Maximum a posteriori estimation)
极大后验估计中加入了一些先验知识,它最大化的是一个后验函数。具体来说,因为贝叶斯定律:
p(θ|x)=p(x|θ)p(θ)p(x)
那么极大后验估计就是要求:
θ^MAP=argmaxθ p(x|θ)p(θ)=argmaxθ{∑Xilog p(Xi|θ)+log p(θ)}
可见,极大后验估计中相对于最大似然估计,多了log p(θ),也就是先验的影响。这一点在Beta分布的后验估计上就能看出来,由于这部分已经写在了这里,所以就不再赘述。
3. 贝叶斯推断(Bayesian Inference)
前面的MAP是一个点估计,只估计似然函数达到最大点的情况下,参数θ的值。Bayesian inference extends the MAP approach by allowing a distribution over the parameter set θ instead of making a direct estimate. Not only encodes this the maximum(a posteriori) value of the data-generated parameters, but it also incorporates expectation as another parameter estimate as well as variance information as a measure of estimation quality or confidence. ——《Parameter estimation for text analysis》
具体来说,给定数据X和需要求的参数θ,贝叶斯推断需要求出一个具体的分布:
p(θ|X)=P(X|θ)P(θ)/P(X)
这里和MAP的区别就在于,MAP忽略了P(X)因为它是常量,对于MAP的过程:求导后再求等于0来获得最好的θ,这个常量是没有用的。但是贝叶斯推断要的是整个p(θ|X)的分布,所以P(X)这个normalisation term是需要被求出来的。在获得具体的分布之后,所要求的参数值可以通过估计期望或方差得到。

Version space

 Ref: http://en.wikipedia.org/wiki/Version_space
A version space in concept learning or induction is the subset of all hypotheses that are consistent with the observed training examples.[1] This set contains all hypotheses that have not been eliminated as a result of being in conflict with observed data.

Version space for a "rectangle" hypothesis language in two dimensions. Green pluses are positive examples, and red circles are negative examples. GB is the maximally general positive hypothesis boundary, and SB is the maximally specific positive hypothesis boundary. The intermediate (thin) rectangles represent the hypotheses in the version space.

2014年7月26日星期六

Train transfers in Belgium/Netherlands

1, find correct platform
2, after getting off the first train, go to the aisle(always below or above the track) to find entrance to next train platform.
3, go to the platform, and see the timetable, find correct train.

Recommend: Belgium Europe SNCB/ mobile app

2014年6月24日星期二

PUF reading

2014-06-24
From [1], soft-decision is better than hard-decision, requiring nearly half the repetition bits for error correction with FRR  10^(-7).  Generate 128-bit key with 3900 SRAM cells, only a single measurement. If multiple Maes et al only needs 1536. 

[1] Vincent van der Leest, Bart Preneel etc, "Soft Decision Error Correction for Compact Memory-based PUFs using Single Enrollment", 2012 CHES