非常值得上的概率课
課程：ELEC2600 [原課號：ELEC210]
作者：xzhuah [14级 CSE]
創建於：2016-06-11 18:14:27
更新於：2016-06-11 18:27:45
課程：ELEC2600 [原課號：ELEC210]
作者：xzhuah [14级 CSE]
創建於：2016-06-11 18:14:27
更新於：2016-06-11 18:27:45
課程時間：2016年Spring季
授課教授：ZHANG, Jun
我覺得教授 可爱的大陆口音教授
授课TA：ZHANG, Xuning
TA极好，是难得的好TA
這門課的Grade：Grade神
我覺得這門課
这门课比MATH2411高到不知道哪里去了，我是CSE专业的，这门课虽然是ELEC，但其内容个人觉得对整个Enginering非常有用。虽然难度不大，但一些非常实用的概念都提到了。我觉得这门课的真正意义在于，它可以被非常容易地运用到其他工科课程里，如果你搞研究，比如UROP涉及到一定量的数据处理，误差分析，你都会发现这门课给力你许多重要帮助。
先从误差的概率分析说起，在工程问题中，如果你要设计一个算法，去测量某个参数，你必须考虑采样的过程。比如我根据接受的信号强度衰减量dR测信号源距离D，dR和D其实是有一个确定的已知关系D=f(dR)的，我必须考虑dR的测量误差。小白们会说，多发几次信号取dR的平均值即可。而学了ELEC2600的同学应该会这样说：
假设：X是一个随机变量，其值为每次试验所测到的信号强度衰减量, 真实信号强度衰减量为dR，则 X=dR+N, N为随机变量，代表环境噪音。N 是iid（independent identical distrubution）,即每次试验中的N互相独立
依据中心极限定理，假设N服从正态分布，平均值为0，方差为s^2
那么假设我们做了m次试验，结果为X1,X2,...Xm
定义 L(d)=P(D=d|X1,X2,X3,...Xm) 就是在测得结果为X1,...Xm的条件下，距离D=d的概率，我们要找到一个d使得L(d)最大
由于D=f(dR)
定义L(dR')=P(dR=dR'|X1,X2,X3,...Xm) 就是在测得结果为X1,...Xm的条件下，距离dR=dR'的概率，我们要找到一个dR'使得L(dR')最大,这个问题等价为上一个问题。
L(dR')=P(dR=dR'|X1,...,Xm)=P(X1,...,Xm|dR=dR')P(dR=dR')/P(X1,...,Xm)，由于P(X1,...,Xm)与dR'无关
最大化L(dR')等价于最大化P(X1,...,Xm|dR=dR')P(dR=dR')，由于根据假设Xi=dR+Ni，所以在dR=dR'的条件下
P(X1,...,Xm|dR=dR')P(dR=dR')=P(X1=dR'+N1,X2=dR'+N2,...,Xm=dR'+Nm)P(dR=dR')=P(N1=X1-dR',...,Nm=Xm-dR')P(dR=dR')，由于假设了N 是iid，所以
P(N1=X1-dR',...,Nm=Xm-dR')P(dR=dR')=P(N1=X1-dR')P(N2=X1-dR')...P(Nm=X1-dR')P(dR=dR'),由于P(dR=dR')是常数，因为在没有任何条件的情况下，dR等于任何数的情况相同。所以，最大化L(dR')等价于最大化P(N1=X1-dR')P(N2=X1-dR')...P(Nm=Xm-dR')
根据假设P(Ni=Xi-dR')=1/((2pi)^0.5*s)*exp(-(Xi-dR')^2/(2s^2)) 写的比较难看，总之就是高斯分布那条啦。
两边取自然对数得
ln(L(dR'))=ln(P(N1=X1-dR'))+...+P(Nm=Xm-dR')=mln(1/((2pi)^0.5*s))-((X1-dR')^2/(2s^2)+...+(Xm-dR')^2/(2s^2))
所以我们要最小化(X1-dR')^2+...+(Xm-dR')^2=X1^2+...Xm^2+mdR'^2-(2dR'X1+2dR'X2+...+2dR'Xm)
ln(L(dR')对dR'求导并令导数为0得2mdR'-2X1-2X2-...-2Xm=0 =>dR'=(X1+X2+...+Xm)/m
到这了，ELEC2600的同学放下笔，微笑着说，当取dR'=(X1+X2+...+Xm)/m时，dR'是真实值的概率最高，小白正要一巴掌扇过去的时候，
ELEC2600的同学又拿起了笔说，我再帮你推推m要多大的时候，我们有99%的信心说|(X1+X2+...+Xm)/m-dR|<0.01
还是假设N服从正态分布 N~N(0,s^2)
令S(m)=(X1+X2+...+Xm)则S(m)=(mdR+N1+N2+...+Nm)
求S(m)的期望E(S(m))=E(mdR+N1+N2+...+Nm)=mdR+E(N1)+...+E(Nm)=mdR
求S(m)的方差var(S(m))=var(mdR+N1+N2+...+Nm)=var(N1+N2+...+Nm)由于根据假设Ni 为iid COV(Ni,Nj)=0 (i!=j)
所以var(S(m))=var(N1)+...+var(Nm)=m*s^2
令M(m)=S(m)/m
则E(M(m))=dR, var(M(m))=s^2/m
利用中心极限定理，M(m)是一系列iid分布的叠加，那它自己接近正态分布，所以M(m)~N(dR,s^2/m)
我们要求
P(|(X1+X2+...+Xm)/m-dR|<0.01)>=0.99
P(|M(m)-dR|<0.01)=P(-0.01<m(m)-dR<0.01)
由于(M(m)-dR)/(s/m^0.5)~N(0,1) 我们可以用Qfunction去解，即
P(-0.01/(s/m^0.5)<(M(m)-dR)/(s/m^0.5)<0.01/(s/m^0.5))=1-2*Q(0.01/(s/m^0.5))))>=0.99
Q(0.01/(s/m^0.5)))<=0.005 近似地0.01/(s/m^0.5))>=2.65
到这了，ELEC2600的同学放下笔，微笑着说， 所以，m>=(70225s^2), 即样本数为噪音方差的70225倍的时候可以满足刚才的要求，
小白正要一巴掌扇过去的时候，ELEC2600的同学又拿起了笔说我们用了中心极限定理，假设了M(m)服从正态分布，但如果假设不成立，M(m)不服从正态分布呢？我们来看看当M(m)为任意分布的时候，m的取值：
还是有E(M(m))=dR,var(M(m))=s^2/m
我们要求
P(|(X1+X2+...+Xm)/m-dR|<0.01)>=0.99
根据ChebyshevInequality
P(|M(m)-dR|>=a)<=s^2/m/(a^2)
P(|M(m)-dR|1-s^2/m/(a^2)
所以P(|M(m)-dR|<0.01)>1-s^2/0.0001m>=0.99
m>=1000000s^2
到这了，ELEC2600的同学放下笔，微笑着说， 所以，m>=(1000000s^2), 即样本数为噪音方差的1000000倍的时候可以满足刚才的要求，
小白崩溃，立志要上ELEC2600
当然上面只涉及到ELEC2600的一小部分，也是比较有用的一部分，其中的maximizelikelihood思想广泛运用在机械学习领域中。
如果我的推导有误，欢迎指正哈！
ELEC2600的课本也是非常理想的习题资源，可以当练习刷。考试可以带cheatsheet，当然理解例题的思路十分重要。
这个课的TA非常好，每次tuto都能见识到很多超好用的技巧，非常值得上，我有时一周两节相同的tuto都跑去听，那些习题很有代表性，值得反复捉摸。教授讲课也还可以，会做很多课堂推导，只是语气比较沉闷，我有几次睡着了。。。当然课件讲的比较清晰，课后可以补。作业量比较大，但占的比重少，偶尔错一点点也没太大关系。
Comments
[3 L]stanab [12级 CSE]
@ 2016-06-11 19:17:56
MATH2411和ELEC2600都上过的飘过虽然我个人非常讨厌MATH2411的教学方法，非常喜欢ELEC2600
但是我还是要声明一点...像po主所说的这个希望以一定确信度(confidence)来用测得的结果(sample)来估计实际分布(population)的话...其实还是MATH2411比较厉害
这么来说...{MATH2411}-{ELEC2600}={outlier,quantile,R,estimator,hypothesis testing,goodness of fit,regression},{ELEC2600}-{MATH2411}={joint distribution,random process(very basic),tail estimation)}
讲道理，切比雪夫，马尔可夫这两个不等式其实不是很紧...做这种confidence test个人感觉可能用处一般，其实这两个不等式再加上切诺夫不等式在算法分析里很有用（因为大O可以drop常数）
真要做confidence test...像文中这个例子...你想确信99%置信区间小于0.01，是可以直接套2411的Confidence Interval，让z(0.495)s/sqrt(n)<0.01就可以了...其中z是z table是inverse of Q table。而且就算你不知道noise的方差(unknown variance)，也可以搞个student t distribution来做置信区间。这样做出来的结果要更紧一点...
虽然我好像吹了一波2411...但是我还是很不喜欢2411...因为讲课方法(不讲原理只讲用法)，考试方法(按计算器)让我深恶痛绝。写这个评论只是想指出，po主对这门课的强项理解似乎稍微有一点偏差...并没有推荐上2411的意思...
[4 L]xzhuah [14级 CSE]
@ 2016-06-11 19:59:18
谭神，现在的2411已经不是你当年学的2411了，这个学期的2411 hypothesis testing,goodness of fit,regression这些都删了，R也不学了，但还是4分课
[5 L]stanab [12级 CSE]
@ 2016-06-11 21:47:10
xzhuah在#4写道:谭神，现在的2411已经不是你当年学的2411了，这个学期的2411�hypothesis test ...
#BlameHKUST
[12 L]xzhuah [14级 CSE]
@ 2016-06-11 23:46:39
Write a comment
請登錄後再評論
請登錄後再評論
