首页
登录 | 注册

可遍历空间 和 不可遍历空间的 算法思想对比总结(不断补充)

数学是外部世界的抽象,只有把数学的方法和真实世界联系在一起才可以真正理解背后的思想:
数学本身是算法的心脏,数学建立起了外部真实世界和抽象模型的对应。
数学又是我们对自然界理解的总结升华。我们对自然界的理解却又是“抽样”!
所以,数学的所有模型都是通过对自然界数据的抽样,猜想,匹配到有限的几类模型中。

总结为一句话:
自然界就是不可遍历的空间,有无数多个实体,每个实体都有无数多个属性。而数学模型就是有限的,有限多的模型。是可以遍历的。

人认识事物的方法根本上只有一种:抽样总结,化无限为有限。如果事物本身是有限的,根本不需要去总结,只需要枚举。
而人类之所以要去总结,
就是认识到了无穷空间中的任何子集都是无穷的。(这样说来有限集合本来就是违背自然界的规律)

扯得有点远,这里言归正传,从计算机算法中“状态空间”的角度谈谈可遍历空间和不可遍历空间模型的区别:

对于所有的不可遍历空间,过去并没有理论性的方法来研究。直到概率论发展完善起来。

无论是计算机可以处理的范围,还是我们可以提供的数据都是有限的。
如何用有限的数据描述无限的状态空间,用一种统一的,一劳永逸的方法,抽象出整个世界?

如果说我们掌握的n多种计算机算法都是在处理有限状态空间,那么遇到真实世界的无限空间我们只能束手无策么?

概率论中 解决 这个问题的方法主要有两个:最小二乘法,最大似然估计!

最小二乘法 : 模型使得 样本点距离误差最小化 。
最大似然估计: 模型使得 样本点出现几率最大化。

对于难以测度距离的空间, 最大似然估计就是不二的选择。

有了这两种方法, 我们才可以建立起各种各样的 模型:
线性回归模型,markov模型,n-gram模型 等等。。

最大似然有一个假设:样本之间是独立的。是完全随机的。这也是经典概率中要求的。
关于最大似然,参看 
http://www.cnblogs.com/liliu/archive/2010/11/22/1883702.html

其实最大似然就是解概率方程组 ,已知样本点, 求解模型参数。颇有一点高中学的待定系数法的感觉。

只不过方程中的相等这里是似然。

下面讲两个问题:似然估计ML和EM,bayesian refference和HMM。最后说明其实HMM就是一种最大后验估计。
还是先从bayesian refference 说起 。
p(a,b) = p(a|b)*p(b)=p(b|a)*p(a)
化简得到:p(a|b)=p(b|a)*p(a)/p(b)
bayes一般用来做决策推断。所以b是已经发生的情况。概率为1.
只需要解决:p(a|b) = p(b|a)*p(a)
p(a):a事件发生的先验概率
p(b|a): 如果是a,则b的概率:故称为 似然概率,是一种假设
p(a|b): b已经发生,则a的概率
仔细体会,可谓非常巧妙。
把bayes应用到该率分析中,抽样分析,寻找隐藏在数据背后模型的参数中:
就有下面的解释:
p(M|D) = p(D|M)*p(M)    M:model   D:Data
似然估计ML:就是假设p(M)是固定的。即模型没有好坏之分,大家一律平等。则p(M|D)=p(D|M)
对于p(D|M),D是一个样本集合,展开一个集合的概率表示:p(D|M)=p(d1|M)*p(d2|M)*......
以上2式:p(M|D) = p(d1|M)*....
求极大的可能对应的M。就叫做最大似然估计。M = argmax(log(pd(d1|M)*......))。
当采集的数据集有未知项时,利用log函数凸函数的性质,在数学上可以证明出先设未知项的值以后求M,再由M更新k(M当然可以更新k。。)是可行的,会逐渐收敛到极值。
这个叫EM。注意是极值。。
这种近似收敛逼近当数据集完全未知时彻底退化掉了。(有人研究么?你要去研究么?)
对于分类问题,kmeans,就是对数据集的种类未知。即真正需要的数据是(D,k),k未知。推演模型M。就先确定k,然后求解模型,然后再更新k。
正是利用了EM。其实EM更像是一个定理,而并不是一种那个方法。EM定义了当数据集中存在未知量时求模型的方法的有效性。而EM的证明是用到ML的表达式。
在用EM方法时,必然隐含着用ML思想求解model。
这个时候你要问了,kmeans没看到求argmax中表达式的极值啊。没看到求一阶导数啊。呵呵。那你必须反思一下自己的思维是不是固话了。求导之类都是方法,
万法为无法,固化于方法是大忌!其实kmeans考虑的是点坐标到模型中心的距离,p(d1|M) 这里正比于距离,而ML中取完log的求和式,形式上完全吻合距离求平均作为中心的kmeans。
集合上有条定理:多个点的几何中心到个点距离之和最小。这。。。还用求导么?

说完了EM,ML,还找了个实际的例子kmeans。我们继续聊bayes refference 和 HMM的关系。
刚才没有提MAP,MAP最大后验估计。比ML更加靠谱。考虑了模型本身的频率。不会出现过匹配情况。
HMM模型大部分情况下都是处理离散model的。但是有处理连续的情况,这是没有关系的。我们就拿离散的讲,一般够平时的应用。
为什么说HMM是MAP呢?

HMM就是隐markov模型!隐含变量就是个markov的状态序列。我们抽样的数据还不是状态数据,中间还有一层简单的概率。即概率的概率。
模型套模型。=。=

什么模型套着什么模型?从我们的角度看,是bayes套着markov。。。

比较特别的是markov,状态概率要看前一个状态。没有固定的函数,是一个动态变化的概率!!!!!
不动就够难了,动了那岂不是更难。其实一动就把Bayes变成了HMM。

如果状态的概率满足一个静态的model。最大似然估计:
p(M|D) = p(D|M)
现在不能这么看了。模型的概率在同时变化,由上一时刻的状态确定。有一个函数M(t) = f(s(t-1)),假设我们算出了上一个时刻的状态s。
这就是状态转移方程!
概率每一时刻在变,根据上一个时刻的状态变。所以:
p(M|D) = p(D|M) *f(s(t-1))
通俗点讲:底层的markov为我们提供了一个状态集合的状态机。每个状态上分布着一个概率模型。概率模型表示着当前状态到其他状态的转换概率。水流,时间,任何变化都可以用这个模型描述!
如果状态是连续的,状态的概率矩阵变化就是连续的!
先不论状态是否连续,看看我们抽样的数据,尝试去推算底层的markov状态机停在那个状态。就是要做bayes refference。

总之HMM就是一个MAP。模型的先验概率实在变化的。。。。。











 


相关文章

  • 第十一章--内核的数据类型
    一.数据类型         u8;         /* 无符号字节(8位) */         u16:     /* 无符号字(16位) */         u32:     /* 无符号32位 */         u64:   ...
  • Java集合详解3:Iterator,fail-fast机制与比较器
    具体代码在我的GitHub中可以找到 喜欢的话麻烦star一下哈 https://h2pl.github.io/2018/05/9/collection3 我的个人博客主要发原创文章,也欢迎浏览 https://h2pl.github.io ...
  • 遍历获得一个实体类的所有属性名,以及该类的所有属性的值 //先定义一个类: public class User { public string name { get; set; } public string gender { get; s ...
  • malloc_chunk边界标记法和空间复用
    malloc_chunk边界标记法和空间复用 边界标记法     ptmalloc分配的空间统一用了malloc_chunk结构来管理,malloc_chunk的结构初看比较奇葩,看了注释,分析了一段时间的代码,发现这种边界标记的设计,在m ...
  • package sortAlgorithm; import java.io.File; import java.io.IOException; import java.sql.Time; import java.util.Random;   ...
  •   1.对数据库进行在线全备 Db2 backup database test online   2.查看备份过程中的表空间状态 db2  "select DBPARTITIONNUM, tbsp _id,substr(tbsp ...

2020 unjeep.com webmaster#unjeep.com
12 q. 0.013 s.
京ICP备10005923号